Semiconductor memory-based server that provides multimedia information on wide area network on demand

Description: TECHNICAL FIELD [Detailed description of the invention]

【０００１】

INDUSTRIAL APPLICABILITY The present invention relates to a method and an apparatus for distributing multimedia data and video data from a server to a requesting client via a communication network.

【０００２】

A system that distributes information and entertainment services to an end user's home has three separate components: a server system, an end user system, and a large number of end users (clients). It has a network that connects to the server at the same time. The two most widely used systems for distributing information to the home are the public switched telephone network and broadcast / cable television systems. The telephone network today provides access to electronically stored textual information such as deposit balances, as well as voice segments such as instructions for various paperwork procedures.

It is widely believed that technological advances will enable interactive multimedia services. Services considered include video-on-demand such as movies, news, sports and TV programming, home shopping, interactive games, travel agency, and a wide range of educational and information services. However, all three components of a traditional information / entertainment distribution system, namely servers, networks, and end-user terminals (PCs or set-top-boxes), are interactive multimedia. Needs improvement to distribute the service. PCs and set-top boxes require the ability to receive and extend full video and accompanying audio. The network must have sufficient bandwidth so that each user has their own dedicated video channel to the server, and for most services the server can simultaneously stream a large number of video streams at low cost. Must be able to distribute.

The main drawback of today's telephone networks is that the bandwidth available to each end user is limited, which is sufficient for at most one voice channel. This hinders the transfer of video-video information and is too slow for high-resolution images. Both cable and broadcast television offer very high bandwidth to each user, but due to the network's limited total bandwidth (cable bandwidth or spectral bandwidth allocated to spatial waves), users themselves. Cannot interactively select information that is of interest to you. Instead, the user's choice is limited to one of about 50 programs that air at any time. Therefore, current telephone networks, as well as both broadcast and cable television networks, are not suitable for distributing interactive multimedia services such as video-on-demand and interactive games.

However, telephone and cable television service providers continue to invest in technological advances to remove these restrictions. The improvement of the integration level in VLSI technology contributes to the cost reduction of video-video compression / decompression hardware, and ADSL (Asymmetric Digital Subscriber). It enabled technologies like Loop). These two results will enable the transmission and reception of video and video at the user's home and the exchange at the local telephone office, providing each user with a dedicated video channel. Similarly, advances in fiber optic transmission technology and its cost reductions have enabled upgrades of cable TV trunks and feeder systems, thereby allowing each active subscriber to receive compressed digital video. Increase network bandwidth sufficiently to provide a dedicated channel to the head end. Direct broadcasting satellites and other emerging wireless communication technologies also provide dedicated video channels between a large number of end users and servers. Personal computers and set-top boxes are also emerging that enable networked multimedia applications by leveraging low-cost video compression / decompression hardware and new powerful and inexpensive microprocessors.

0006 End-user (client) systems and network infrastructures are evolving rapidly to meet the demands of interactive multimedia services, but the servers currently in use are still expensive, and each Due to the limited number of streams that can be supported by the server, it is not practical to distribute these services. Previous choices for servers for interactive multimedia services have been off-the-shelf (packed and ready-to-use) mainframes or workstation technology-based parallel computer systems. The hardware and software in both cases are optimized to support computationally intensive applications and multiple simultaneous users (time sharing), with respect to data transfer to and from network interfaces and I / O devices. I don't attach much importance to it. For example, the memory-to-cache bandwidth on the RS / 6000 is 400 Mbytes / sec, while the input / output or network device-to-system bandwidth is only 80 Mbytes / sec. Floating point support boosts system costs without providing any benefits for video / multimedia data distribution. Network protocols are used for reliable data transfer in unreliable slow network links, network infrastructure, and application environments in the early 1970s, contrary to the reduced reliability requirements for video on better modern networks. Optimized for, leading to unnecessary CPU overhead.

The above factors make the price / performance of a general purpose computer system based video / multimedia server more expensive / advanced compared to a system optimized for video distribution. Well-known activities pointing out the above limitations have been minimized to date, specifically optimizing the placement of data on disk arrays to maximize disk throughput in video server applications. Cases (see references [3] and [4]), and cases where the policy for buffering data retrieved from the disk is optimized to maximize reusability in a video server environment (references). (See [5], [6]), or limited to cases where the file system is optimized for video data (see reference [7]). These improvements can improve the price / performance of current video server systems by a factor of two to four, but 100 times to make interactive multimedia services economically feasible. Up to 1000 times improvement is required.

Two patents by Hoarty et al. (US Pat. Nos. 5093718 and 5220420) use multiple servers, each serving adjacent clients, and a complete multimedia program offloads these servers. Propose a case to be done. In contrast, the present application uses a large server that offloads only the video content distribution portion of a multimedia application to a switch or router in the network. Application control, i.e. determining which video sequence to play and when to play it, is maintained as a support function of the central server, similar to billing.

U.S. Pat. No. 5,287,507 by Hamilton and Nelson points out a problem that occurs when one client wants to send a reference to some information to another client, not to a copy stored in the server. Pass it to a copy of the information stored in the local cache. This allows the receiving client to reconstruct a pointer that points to the information stored in the server. The distribution mechanism of the present application does not presuppose the existence of a local cache, and therefore the above patent is not relevant to the present invention.

US Pat. No. 5,500,122 by Griffen et al. Proposes the use of server computers in networks containing a large number of client computers to provide services such as backup, software distribution, and the like. This does not point out the design of the server for the distribution of continuous media information.

US Pat. No. 5,218,697 by Chung proposes a method of providing a central file server in dissimilar file servers running different operating systems, different file servers, and networks of different file systems. .. Chung is central to the local server, rather than the traditional method in which the local file server sends a file server request to the central file server, which must translate it into the appropriate file system command. Teach you how to access the central server's file system directly by sending file system commands to the server.

U.S. Pat. No. 5,287,461 by Moore deploys servers remotely. This method multiplexes the console lines of multiple servers and uses a modem to send the multiplexing information to the desired location.

U.S. Pat. No. 4,897,781 by Chang et al. Teaches a network file system in which a client has a local cache for open files. This patent teaches how to use information already cached from one file for another access to the same file generated by different open commands.

【００１４】

PROBLEM TO BE SOLVED: To provide an interactive multimedia service on a communication network at a low cost.

A more specific object of the present invention relates to the efficient distribution of video content to requesting clients by offloading the video content to a switch on the network and the distribution of video content from the server to the requesting client. It is to reduce the overhead.

【００１６】

[Means for solving problems] The present invention proposes a method of reducing the distribution cost of a video stream by 100 to 1000 times as compared with the conventional approach by improving the network. The improvements proposed here allow video / multimedia content to be stored in network switches or routers in the form of network packets. The multimedia application server sends a control message to a switch or router that stores network packets that correspond to the requested video or multimedia information, and one or more of these packets are sent to the designated client. A switch or router that receives these instructions retrieves the request packet and, if possible, the header of the packet and, if possible, trailer information, in particular for the network to transmit these packets through a set of routers and switch to a designated client. Change the routing information and send these packets over the network. In order to support a large number of streams on the order of tens of thousands, pre-packeted video is stored by a semiconductor storage device, packets are searched by special purpose hardware, and header information is changed. See the description of the video dispatcher in FIG. 4 and the stream control and output adapters described below. Semiconductor storage devices can be augmented with disk storage devices that store less popular video content. Only disks are available to support hundreds to thousands of few streams, and microcontrollers / microprocessors instead of special purpose hardware to retrieve packets and change header information. Can be used.

【００１７】

[Examples] In the examples described later, the use of a switch for offloading video / multimedia or continuous media contents will be described, but such a description can be easily applied to the use of a router / bridge or the like instead of the switch. Can be transformed. Further, although the use of a packet-switched network that transfers only fixed-size cells will be described here, the examples described later can be easily adapted to use in a network that transfers variable-sized packets or a circuit-switched network. In this embodiment, an ATM (asynchronous transfer mode) broadband network and an AAL5 (ATM adaptation layer) adaptation layer are used (see Reference [1]). Finally, in this embodiment, only the distribution of video information stored in a compressed format will be described, but those skilled in the art will also be able to understand uncompressed video information and other continuous media information such as audio and video. It will be understood that it can be processed without change. Different audio or video information can be compressed at different rates. For example, music can be compressed at a higher bit rate (lower compression ratio) than voice. The continuous media stream is MPEG-II (Motion Picture Expert). Group) Contains multiple streams of different media types that are multiplexed as transport streams. In this embodiment, an MPEG-II transport stream that carries one video and one audio channel as video content is used. It is assumed here that each second of this video is compressed into 4 Mbit digital data.

The embodiments of the present invention have two distinct elements. The first element is the offloading of video content from the host or application server to a switch in the network, and the second element stores the video content and, when commanded by the host, directs it to the designated client. Switching hardware that can be dispatched. From now on, the format in which the video content is stored in the network, and to minimize the hardware required in the switch to retrieve and dispatch the video content to the client, is stored with the video content. Additional data will be mentioned. In addition, a shared buffer is used to store the video in a semiconductor storage device, perform operations to allocate and reclaim this storage device, and to support retrieval and dispatch of video content when requested by the host. -Hardware changes / additions required within the switch are also described. The last section briefly describes another embodiment of the invention in which network switches other than shared buffer switches are used and disk storage is used instead of semiconductor storage.

0019 Offloading video content from the host to a switch in the network: With reference to FIGS. 1 and 2, the first step of the present invention is to switch 60 (FIG. 2) of the ATM broadband network 50 with video content 900 (FIG. 3). Including offload to. The MPEG-II transport stream for a one-hour program is about 1.8 gigabytes of digital data 900. When stored on a general purpose computer running on an operating system such as UNIX, this data 900 is segmented into 4K byte pages 901 (Figure 1), each of which has about 450,000 pieces of data with 4K bytes. -It is stored in a magnetic disk or the like including the block 910. In addition to these data blocks representing video content, other information collectively known as metadata can be stored on disks such as Inode 911 and Indirect Block 912 (see reference [2]). .. This metadata (shown in FIG. 1) is stored separately from the video content. That is, it is stored in a disk block different from the disk block that stores the video contents. This metadata is used by the operating system to place pages that belong to a particular video file and to store pages that store specified area data in a video content file.

0020 Referring to FIG. 8, a request message 6 transmitted from the client 20 to the host 10 via the switch 60 of the network is shown. This request message is preferably a remote procedure call with multiple parameters issued by the client to call the video distribution procedure on the host. The first parameter of the request message is the name or index of the video file requested by the client, which is performed by the server early in the execution of an interactive multimedia application running in a distributed computer environment of the client and server. Selected from the list of available video files provided to the client. The second parameter in the request message specifies the offset from the start of the video file where the video file starts playing. The third parameter in the request message specifies the offset from the start or start offset of the video file where the playback of the video file ends. Yet another parameter specifies whether the offset in the third parameter is related to the start of the video file or the relative playback start position. Offsets within the second and third parameters can be expressed as time or number of data bytes. Since remote procedure calls are known, we will not touch on request messages anymore (see reference [8]). The host processes the request message and determines if the request video content is stored on one of the network switches, as described below. If stored, the host sends a control message 8 containing the request data to the switch (see references [2], [6]). In response to the control message, the switch looks up the video packets specified in the control message and distributes these packets to the client.

0021. FIG. 2 shows a high-level diagram of the system of the present invention, including a host 10, a client 20, and a network 50 with a plurality of switches 60. In order to offload video content 900 (see Figure 1) from a host or application server (usually a general purpose computer), the present invention divides video content 900 into a fixed size payload 915 for generating video message 920. (See Fig. 3). The payload size is typically 1 Kbytes to 16 Kbytes and is selected to be 1528 bytes in this embodiment. A payload of this size fits into 32 ATM cells 930, as shown in FIG. Each payload in the host or application server is replaced by a pointer 925 containing the network switch address 926 and the message address 927 in the switch (see Figure 2). The size of each such pointer can be 8 to 16 bytes. The video message 920 itself, represented by the pointer 925 in the host, is at the message address specified in the pointer in the switch 60 specified by the switch address element 926 of the pointer, as shown in FIG. Be remembered.

Because the files in the host containing the video content 900 are different from the files containing the pointer 925 pointing to the video message stored in the switch on the network, and the host must use these files differently. The host uses a naming translation that assigns a particular file type to all files containing video content 900 and another file type to all files containing pointers to video messages stored on the network. Alternatively, the host holds a table with an entry that lists all the video content files and indicates whether the files are video content or a list of pointers to video messages stored on network switches. can do.

Before storing the video content in a switch in the network, an 8-byte ATM AAL5 Convergence Sublayer (CSL) Trailer 931 is added to each payload 915, as shown in FIG. It is reformatted into a video message 920 containing a series of ATM cells 930 (in an ATM network, network packets are called cells). Similarly, in non-ATM packet-switched networks, after the transport layer header / trailer is added to the message, segmentation is performed as needed, and before the message is stored on the switch, the network layer header and ( Or) trailers are added to these segments.

Fields in the network / transport / adaptation layer headers or trailers that can be precomputed when the packet is stored in the switch are precomputed and stored in the ATM cell at the appropriate location. In the present invention, the last packet of each message has an 8-byte convergence sublayer (CSL) trailer 931 in which the message length field and checksum field are pre-populated before the message is stored in the switch. It is calculated and the inter-user instruction (UU) field and the intersection instruction (CPI) field are set to zero. These four fields represent a complete ATM AAL5 / CSL trailer. Within the 5-byte header 935 in each ATM cell, only the last half byte can be pre-computed. These 4 bits include the cell loss priority and payload type, and the payload type is AAL5. Includes the 1-bit end of the datagram field in the SAR (Segmentation and Reassembly) layer. As mentioned above, the ATM cell 930 with a partially pre-computed header / trailer contains pre-processed video packets.

The video message 920 is a basic unit of flow control in the network and, as a result, a basic scheduling unit in accessing video memory and transmitting video data to clients. If the ATM cell retrieved from video memory is not the last cell in the video message, the switch automatically schedules the retrieval of the next cell in the video message. The ATM cell of the video message is received by the client as a burst. This is because the switch does not insert a delay between the transmissions of the two ATM cells of the video message to control the transmission rate. The size of the video message needs to be limited for efficient network operation, that is, to provide fast response time in interactive multimedia applications and to minimize buffer requests on the client. .. However, short video messages can require frequent dialogue between the host and the switch, requiring a stronger (and therefore more expensive) host and hardware in the switch that can handle a larger number of control messages. To do.

0026 The above problem is solved by allowing the switch to send multiple video messages to the client in response to a single control message received from the host. To support this feature, additional information is generated for each video message and stored in the video message in the network switch. This information includes a link field 940 and a flow control field 950 (see FIG. 3). The link field 940 in each video message 920 of the video stream 900 points to the next video message in that stream. Thus, the host or application server can send a control message to the switch that specifies the address of the start message and the number of messages to be sent subsequently, and the switch uses the link field 940 to search for subsequent messages. be able to. The flow control field 950 includes the playback time of the next video message when referenced from a fixed start point. Therefore, the switch can insert the correct delay between the transmission of two video messages in the same stream in order to maintain an appropriate rate for the distribution of video data to the client.

Change Switch Hardware and Its Operation: This section first briefly describes the design and operation of the shared buffer switch that is the basis of this embodiment. Next, changes are described to provide the switch with the ability to store video and the ability to dispatch designated video packets to designated clients when instructed by the host. When first describing a switch that does not change, this is not directly related to this embodiment, but the relationship with this embodiment will be clarified in the description of the modified version of the switch described later.

[0028] Shared buffer switch: Figure 4 shows the high-level architecture of a shared buffer switch. A large-capacity shared memory 400 exists in the central portion thereof, and an input bus 300 for writing data to the memory and an output bus 350 for calling data from the memory are connected. Both the input bus 300 and the output bus 350 have a width of 53 bytes, which is equal to the size of the ATM cell in this embodiment. The packet (ATM cell) arriving over each high-speed serial link 100 is processed in the input adapter 200, the ATM cell header is examined to determine the switch output 150 on which the packet must be routed, and the ATM. According to the networking method, the cell address (VPI (virtual path identifier)) field and VCI (virtual circuit identifier) field are swapped (see reference [1]). After this processing, the input adapter 200 deserializes the packet into a single 53-byte wide word and outputs it on the input bus 300. At the same time, the input adapter 200 outputs the address of the switch output 150 on which this packet must be forwarded on the output address bus 310. The packet is then stored in a location in shared memory 400 that is independently determined by the central controller 500. The bus bandwidth matches the total bandwidth of all input signal lines. The shared memory 400 is configured as an array of 53-byte words 410. That is, the basic unit of data transfer in read and write operations is 53 bytes, which is equal to the size of an ATM cell. For the sake of brevity, these 53-byte words in shared memory will be referred to as cells. Each output link 150 has an associated output adapter 250. The output adapter 250 corresponding to all output links is connected to the shared memory by the time division multiplexing bus 350 in the same manner as the bus 300 shared by the input adapter 200.

[0029] A list of free cells in shared memory 400 is maintained by control section 500. This list is kept in the FIFO queue 510. Each output link 150 has a corresponding FIFO queue 520 within the control section 500. These queues are logically separate, but can be implemented using a single physical memory. Queue 520 stores the address of an ATM cell that the corresponding output adapter must retrieve from shared memory and distribute to the network. In order to store the input packet in the shared memory, the address of the free cell is obtained from the free cell list 510 and output on the write address bus 530. At the same time, this address is dequeued (dequeued from the queue) from FreeCell List 510 to the address queue 520 selected by the output address bus 310, which carries the address of the switch output 150 to which the packet is sent. Enqueued (waiting in the queue). The output adapter 250 dequeues the addresses of the packets stored in the shared memory transmitted to those output links 150 from the corresponding address queue 520 of the central controller 500, reads the packets from the shared memory, and serializes them. And transfer it onto the output link 150. The address of the packet dequeued from the address queue 520 is output on the read address bus 540 and simultaneously recycled (recycled) in the FreeCell list 510.

[0030] The bandwidth of the input bus 300 is equal to the combined bandwidth of all the input links 100. Therefore, arbitration of the input bus 300 is unnecessary. Instead, the bus is operated in slot format and each of the N input adapters accesses the bus every Nth slot. In this embodiment, the slot corresponds to a clock cycle. The output bus 350 is also operated, and the input and output adapters interact with the central controller only within a clock cycle that gains access to the input or output bus. A microprocessor 210 is shown in each input adapter 200, and a microprocessor 260 is shown in each output adapter 250. They are used to perform various link monitoring and service functions, and the microprocessor in the input adapter is also used to manage the routing table. These will also be used effectively to service the video streams distributed by the switch in subsequent discussions. Control point 600 is a workstation or PC-class general-purpose computer that performs network management functions such as maintaining a database of network-wide topology, link state and link utilization, assigns labels to newly established lines, and Used for initialization and monitoring of microprocessors 210 and 260. Control points are also effectively used in subsequent discussions to allocate and reuse memory used to store video content.

Finally, for ease of explanation, it is stated here that the shared buffer switch has a separate input and output adapter, each with a microprocessor, and a separate input and output bus. In a compact form, these two adapters are combined into a single card, with one microprocessor servicing both adapters, and a single bus with twice the bandwidth of the input and output buses. Input and output buses can be replaced.

A shared buffer switch modified to store video and distribute it to clients in response to instructions from the host: FIG. 5 shows the storage function of video message 920 and from host 10. The hardware changes required in the shared buffer switch to provide the function of distributing the messages of the designated group to the designated client 20 in response to the reception of the control message 8 are shown. A video memory 700 is added to the shared buffer 400 in order to store the ATM cell 930 of the video message in the shared buffer switch of FIG. The shared buffer 400 and the video memory 700 share input and output buses, an address bus, and write permission control. The link field 940 and the flow control field 950 are separately stored in the tag memory 810 existing in the video dispatcher 800 (see FIGS. 5 and 6).

0033 The video dispatcher 800 is shown in detail in FIG. The video dispatcher 800 can receive the ATM cell containing the control message 8 (see FIGS. 7 and 8) directly from the host 10. These control messages are received from the input bus 300 by the interface logic 870 when the input adapter 200 activates the signal 717. Each control message 8 is the address of the first ATM cell in the video message group, the time when the first video message in that group should be distributed, the video in the group, as shown in FIG. Designated by central controller 500'by specifying the number of messages, output adapter address, and stream number and issuing a request to the video dispatcher for one ATM cell at a time to central controller 500'. Requests the output adapter 250'to distribute all ATM cells in the group. The request to read the ATM cell is enqueued to the dispatch queue 825 by the scheduler 815 via the multiplexer 820 at the time specified in the control message. The video dispatcher also receives similar instructions from the microprocessor 260 in the output adapter 250'on bus 270 by interface logic 871 without encapsulation into an ATM cell. As with the interaction with the central controller, the input and output adapters interact with the video dispatcher only in the cycle of accessing the input bus 300 or output bus 350, so that arbitration occurs on buses 270, 271 and 717. Not required. The use of these buses will be described in detail below. When the distribution time of the first message of a message group is specified in the video dispatcher, the distribution time of each remaining message is obtained from the flow control field of the previous message stored in tag memory 810. ..

0034 The video dispatcher 800 has a FIFO dispatch queue 825 that stores read requests for ATM cells from the video memory 700. The ATM cell cannot be enqueued to the immediate central controller 500 due to a conflict with the address queue 520 from the input adapter 200. Each entry in the dispatch queue 825 has three fields. The output adapter address field 826 indicates an output adapter 250'that receives the cell read from the video memory 700 in response to this read request, and the stream ID field 827 is the adapter specified in field 826 from which the cell is read. Specifying the video stream above, the video memory address field 828 specifies the address in the video memory from which the cell is read. When the bit on the signal line 315 of the output address bus 310 of FIG. 5 is inactive, this indicates that there is no input adapter interacting with the central controller and the entry is dequeued from the dispatch queue 825. .. The contents of the output adapter address field 826 are output on bus 745 to select the address queue 520 in the central controller. The remaining fields, the stream ID field 827 and the video memory address field 828, are output on bus 725, multiplexed with the input to address queue 520, and the address queue selected by the address on bus 745. It is stored in 520.

The video dispatcher also monitors the addresses of all cells read from the video memory on bus 540, as well as the output adapters and stream IDs to which they belong, on the cell address monitor 850. Signal line 581 indicates that the cell has been read from video memory. If the cell just read from video memory is not the last cell in the message, incrementing the cell address with the incrementer 855 will generate a new request, which will be sent via the multiplexer 820 to the dispatch queue 825. Will be sent to. If the cell read from video memory is the last cell of the message, the link and flow control fields of that message are read from tag memory along with the stream ID received from bus 540 to read this message. It is transmitted to the receiving output adapter 250'. This information is transmitted over bus 271 and triggers microprocessor 260 in output adapter 250'to request a new message from video memory.

0036 ) Is changed as follows. A multiplexer 720 is provided between the FreeCell list 510 and the address queue 520. One input of this multiplexer is bus 530, which carries the address of a free cell in shared buffer 400 that is written in the current cycle by a particular input adapter, and this address is the address addressed by output address bus 310. -Must wait in queue 520. The other input is bus 725 from the video dispatcher 800, which carries the address of the cell in video memory and the identification number of the stream, both of which are the address queue 520 identified by bus 745. Must wait for. One bit on the signal line 315 of the output address bus 310 indicates that the output address is valid and is used to provide the bus 530 with higher priority and control the multiplexer 720 accordingly. The control bits 315 also use the output address 310 when bus 530 is selected, and on bus 745 by the video dispatcher when the content stored in address queue 520 is selected from bus 725. Control the address multiplexer 720 in the central controller to use the generated address. In this embodiment, the video dispatcher is blocked from writing to the address queue 520 even when the contents of the bus 530 are written to different address queues 520. This drawback can be avoided by providing more complex logic. Addresses dequeued from address queue 520 are recycled to FreeCell List 510 only if they are addresses in shared buffer 400. The control logic 730 checks whether the address on the bus 540 is within the address range of the shared buffer, and enqueues only the address within this range to the FreeCell list 510. The address of the video memory 700 has more bits than the address of the shared buffer 400, and the video memory

Loading Video Memory from the Host: A load address bus 760 is used with the control bit 761 to load information from the input adapter 200 into the video memory 700. The microprocessor 210 in the input adapter 200 receives a message from the host and loads the sequence of ATM cells contained in the message from a starting address in video memory. This starting address is also specified in the message. In response, ATM cells are output on the input bus, the address of the video memory in which these ATM cells should be stored is output on the load address bus 760, and control bit 761 is activated. To. Control bit 761 controls the multiplexer 710 in central control measure 500'so that the write address 532 of the video memory is selected from the load address bus 760 rather than from the FreeCell list on bus 530. To do. When control bit 761 is active, control bit 315 is inactive, allowing the video dispatcher to access address queue 520.

The general purpose computer 600'used as a control point in the shared buffer switch also functions as a video storage manager for allocating and reusing video storage. The host computer or application server interacts with the video storage manager to request a block of free video memory or return a block of video memory. When the video storage manager allocates a video memory block to a host and notifies the host with the address range corresponding to that block, the host is allocated without further interaction from the video storage manager, as described above. Can be written directly to the video memory. The write instruction command from the host to the video memory 700 is transmitted directly to the microprocessor 210 or indirectly via the control point processor 600'to the microprocessor 210.

Since the video storage manager is a general purpose computer, communication between it and the host can occur using any standard reliable transport protocol and the desired security and verification means can also be used. .. Messages from the host to the microprocessor 210 in the input adapter 200 can also be distributed over secure links, key distribution is processed by the video storage manager, and message decoding is performed within the microprocessor. Will be done. Two common types of messages sent from the host to the microprocessor 210 are for loading video memory and sending commands to the video dispatcher. The microprocessor 210 may be programmed to return an acknowledgment to the host if these command messages contain the appropriate information to send an acknowledgment. Video memory fragmentation is a proposed buddy system for allocating main memory in multiprogrammed computers. By using method), it can be processed without requiring compression.

Distribution of video data from video memory to end users: As described above, control message 8 sent by the host to distribute a group of video messages is intercepted by the input adapter 200. The input adapter 200 then transfers this command to the video dispatcher 800. For each ATM cell in this group of video messages, the video dispatcher presents a separate request to the central controller to read the ATM cell and distribute it to the correct output adapter. The output adapter must fill the VPI / VCI fields in these headers before the ATM cells read from the video memory are sent over the output link 150.

When the ATM cell is read from the video memory 700 and distributed to the output adapter 250'(see FIG. 10), the video dispatcher receives the stream ID of this cell from bus 540 and the stream ID on bus 271. Transfer to the output adapter via. If the ATM cell distributed to the output adapter is the last cell of the video message, the link field 940 and the flow control field 950 are also transmitted along with the stream ID. The output adapter completes the header of the ATM cell that is simultaneously received from the video memory, as described below.

The output adapter can generate an acknowledgment indicating the successful transfer of the video message for return to the host. For efficient implementation in large servers, this acknowledgment must be generated by the hardware with the return address from the stream control table and other relevant information. Except when the number of ATM cells in the message group is large enough and therefore the frequency of acknowledgments can be processed by microprocessor 260.

[0043] Suitable Implementation of Video Memory: In a preferred embodiment, the shared buffer 400 is implemented by a static random access memory (SRAM) module. However, video memory is much larger than shared buffers, so cost, power, and space limitations (shared buffers are several megabytes in size, while video memory is on the order of hundreds of gigabytes). Therefore, it cannot be realized by SRAM technology. Therefore, the video memory 700 is implemented by the dynamic random access memory (DRAM) module 710, as shown in FIG. Preferably, there are 4 to 16 DRAM modules, each module having a width of 53 bytes. In this embodiment, 4 modules are used. Since the DRAM module does not have a separate data input port and data output port like the SRAM module, the tristate driver 711 is used to connect the data port of the DRAM module to the input bus 300 and the output bus 350. And 712 are used. The multiplexer 420 is used to multiplex the read address 540 and the write address 532 onto the address bus 425. The write permission signal 585 controls the multiplexer 420 and also provides write permission control for the SRAM and DRAM modules.

The DRAM control device 750 uses the address received from the address bus 425 to generate an address signal and a chip selection signal for each DRAM module. Further, the DRAM control device 750 generates a row address selection signal and a column address selection signal for the DRAM module, and provides a memory refresh signal.

The data access time of the SRAM is much shorter than the data access time of the DRAM. The address provided to the SRAM imposes equal access times on both the SRAM and the DRAM and is delayed by the delay element 410 to avoid conflicts with the output bus 350. If an access request to a DRAM module is not immediately accepted because the DRAM module is busy with a previous request, the request acceptance signal 581 is turned off, thereby preventing the address from being dequeued from address queue 520. It tells the video dispatcher 800 that the video packet is being sent to the output adapter. ATM cells in video memory are interleaved across the DRAM module.

Output Adapter: The high-level architecture of the modified output adapter 250'is shown in FIG. The ATM cell is received from the shared buffer or video memory via the output bus 350 every N clock cycle. Where N is the number of output adapters. The logic block 282 serializes the ATM cells received on the output bus 350 onto the 32-bit or 16-bit wide bus 283. The logical block 284 monitors the bus 271 driven by the video dispatcher 800 when the ATM cell on the bus 283 comes from the shared buffer 400. In this case, the ATM cell remains unchanged and is passed to the output link interface logic 288 via the multiplexer 286, which finally transmits the ATM cell onto the output link 150.

If the ATM cell on bus 283 is coming from video memory, bus 271 will include the stream ID of that cell. The stream ID is output on the bus 285 by the logical block 284, and the stream control table 280 is indexed in order to search the header information of the ATM cell. This header information is transferred to the multiplexer 286 via the bus 289 and is substituted by the multiplexer 286 in the ATM cell received on the bus 283. The control signal 287 generated by the logic block 284 causes a substitute for this header.

The logic block 284 scans the header of each ATM cell received from the shared buffer 400 to determine if the ATM cell is addressed to the microprocessor 260 on the output adapter. When addressed, the ATM cell is not transferred to the output link interface logic 288 but is transmitted to the microprocessor 260. This is the main mechanism for the host 10 to communicate with the microprocessor 260 and manage the stream control table 280. The two main commands sent by the host to the microprocessor 260 are the creation of new entries in the stream control table and the clearing of entries from the stream control table (see Figure 8). The microprocessor 260 uses the local memory 261 to store its programs and data and interacts with the logical block 284 to cause changes to the stream control table. The host sends commands for managing the stream control table directly to microprocessor 260 or through control point processor 600.

It has already been mentioned that the switch must distribute multiple video messages to the client in response to each control message received from the host. One method for verification is to have the host request the distribution of multiple video messages with a single control message, as described above.

0050 Another method is to specify the message count for each stream in the stream control table, stop the time, or stop the link pointer value. The host initiates the stream by sending a control message to the video dispatcher and specifying the distribution of the first video message. When the last ATM cell of a video message is processed by the output adapter, the message count of the stream stored in the stream control table is decremented, or if a stream stop time is specified instead. The stop time is compared to the stream distribution time, or the link pointer stop value is compared to the link field received on bus 271. If the outage condition is met, an appropriate acknowledgment is generated and sent to the host. Otherwise, the link and flow control fields are used to generate a new request to read the next video message for that stream, and the new request goes to the video dispatcher via bus 270. Will be sent. When the host receives an acknowledgment of the stop condition, it sends a command to the output adapter to reset the stop condition in the stream control table, and controls to send a video message following the last message distributed in the stream. Distribution of the video stream can be continued by sending the message to the video dispatcher.

0051 Providing the two different methods described above for a host to request the distribution of multiple video messages may seem unnecessary at first. However, in the first method, the host requests multiple video messages within the control message sent directly to the video dispatcher, and the short video stream is very small compared to the second approach. You can have a latency startup. The second approach, on the other hand, has high startup latency because the exact stop condition must first be set up in the stream control table before the host can start distributing the video message to the client. However, the drawback of the first approach is that when the host sends a control message to the switch instructing the client to send a specified number of video messages, the host completes the distribution of all the video messages by the switch. Cannot be interrupted and the playback mode cannot be changed until all video messages have been distributed. On the other hand, the host can change the stream control table at any time to change the playback mode, stop conditions, or to specify a new start point. The first approach is suitable when the application requires the host to interact frequently with the switch. This approach provides low overhead and stream startup latency. The second approach is suitable when the interaction between the host and the switch is rare. This approach allows the host to retain control of the transfer of video messages.

Support for reverse playback, fast forward and fast rewind: The above description describes how to distribute video in regular playback. To achieve this, one link field and one flow control field were used. To support multiple playback modes, multiple video messages require multiple link fields and multiple flow control fields. This section first describes how video messages are linked together to support multiple playback mode. This is often done using multiple links within each video message. Each link field is always associated with its own flow control field, which specifies the delay that the switch should introduce when scheduling the video message indicated by that link. Following the message linking method, a space-efficient method for storing link fields and flow control fields in the switch will be described.

In a video stream compressed by the MPEG algorithm, there are three types of compressed frames: Intra coded, Predictive coded, and Bidirectionally predictive coded. There is. The internal coded frame (I frame) can be decoded without additional information, but the decoding of the predicted coded frame (P frame) requires a preceding decoded I frame. Decoding a bidirectional predictive coding code (B frame) requires a subsequent decoding I frame or P frame in addition to the preceding decoding I frame or P frame.

FIG. 15 shows a frame (picture) sequence within a video stream. This corresponds to the order in which frames are captured and displayed, which is referred to here as the presentation order. However, it will be easily understood that the second frame, which corresponds to the B frame, cannot be decoded until the first P frame or the fifth frame, which is the I frame following this frame, is decoded. Therefore, the order in which the frames of the video stream are decoded (referred to as the decoding order) is different from the presentation order. Referring to FIG. 16, the arrows indicate the decoding order of the frames listed according to the presentation order from left to right. In this embodiment, the compressed picture frames in the video stream are stored in decoding order and thus transmitted to the client in decoding order. In the video message accessed by forward link 941, the compressed picture frames are represented in decoding order.

0055 To support reverse playback of the video, the compressed picture frames shown in FIG. 17 (listed from left to right according to the presentation order in forward playback) are sent to the client and in the order shown by reverse link 942. It is decrypted with and displayed by the client from right to left. If a reverse link is used to access the video message, the compressed video frame will appear according to the decoding order for playing the video in the reverse direction, as shown in FIG. Since video messages are fixed in size, the start and end of picture frames are not aligned with the video message boundaries. Therefore, when the video messages are accessed in a different order than the regular playback modes, such as reverse play, fast forward and fast rewind, the first and last video messages in the video frame contain extra data. become. In this case, the client must be programmed to discard the extra data, or the embedded bytes must be used in the video message to align the picture frame boundaries with the video message. Reverse links are not remembered with video messages that do not include the end of the frame. This is because in these frames, the forward link and the reverse link are the same.

0056 Fast forward and fast rewind functions are supported as well as reverse playback. Referring to FIG. 18, link 943 links the last video message containing the I-frame data to the first video message containing the next I-frame data. A fast-forward effect occurs when link 943 is used to access data, an I-frame is retrieved, and the I-frame is distributed to the user at a rate faster than the rate received by the client during regular playback. Achieved. In regular playback, the client typically receives two I-frames per second, so this method is useful if the fast-forward speed is about 15 times the normal playback speed. To support slower fast forwards, all I and P frames may be linked by link 944, as shown in FIG. Links 945 and 946 are similarly used to support the rewind function at two different speeds, as shown in FIG. Again, links 943 and 945 are in the video message containing the end of the I-frame, and links 944 and 946 are in the video message containing the end of the I-frame or P-frame. If these links are not remembered in the video message, forward links are used. Finally, links 943 and 944 have their own flow control fields that can be shared by links 945 and 946, respectively.

Since each video message has a different number of link fields, it is wasteful to provide storage for the maximum possible number of link fields within each video message. To minimize request storage, link fields are compactly stored in tag storage within the video dispatcher, along with flow control fields, and a fixed-size pointer pointing to the link for each video message is a video. -Stored in the tag pointer storage area added to the dispatcher. The address of the video message is then used to get a pointer from the tag pointer storage area, and then this pointer is used to access the link corresponding to the video message from the tag storage area. Each entry in the tag pointer storage has a mask entry in addition to the pointer to the tag storage. The mask indicates an existing link.

Finally, an extra field is added to the control message sent from the host to the video dispatcher to support reverse, fast forward and fast rewind playback modes. This field specifies the playback mode. The playback mode information is transmitted on the buses 725 and 540 together with the ATM cell address (and stream ID) and stored in the address queue 520 together with the ATM cell address. Therefore, when the last ATM cell of a video message is retrieved from video memory, the link to the next video message and the corresponding flow control field are stored corresponding to the previously transmitted video message. It is selected from a series of links using the playback mode information.

Another Example: The embodiment described in the section above uses a shared buffer switch design, the video storage is implemented as an extension of the shared buffer itself, and the video retrieved from the shared storage. The packet (cell) was forwarded to the switch output adapter. In this section, we will briefly describe three other aspects of the above embodiment, each storing pre-packeted video information in a switch in the network.

If buffers are provided within the output adapters of the switch and the processing power available in these adapters to perform the general functions of the output adapters, even video storage devices that are not based on a shared buffer design. , Can be connected to this switch. 11 and 12 show common methods of integrating semiconductor memory into such switches. FIG. 11 shows a generic switch having an input link 61, which has an output queue 1250 in addition to the switch hardware 1000 and its control circuit 1150. FIG. 12 shows a video memory 700 added to this switch, which is directly connected to the output queue via the video dispatcher 800. Unlike the embodiments described above, the video data is sent by the video dispatcher to the output adapter, which reaches the output adapter via a different bus than the legitimate network traffic. The video memory manager 1600 also receives the video data and writes it to the video memory 700. Other operations are the same as in the above embodiment based on the shared buffer switch.

[0061] As mentioned above, if the semiconductor memory cannot be directly connected to the output adapter, the input link of the switch is used to connect the semiconductor storage device, as shown in FIG. The video storage device 700'' is multiported by the port 800'' connected to the input of the switch. The input adapter is modified to include video dispatch logic. Each modified input adapter 200'' has a stream control table to handle the video dispatch function for video streams accessed through this table. The output adapter 250'' is similar to the 250, except that the interface to the switch hardware is no longer a wide shared bus. This approach has the disadvantage of requiring more switching hardware to support the same throughput as the video travels through both the input and output adapters. In contrast, in the design described in the previous section, the switch can have fewer input adapters. This is because the traffic is exclusively video data that is integrated directly into the output adapter. A small number of input adapters used saves not only the input adapter hardware, but also the availability of smaller switches.

Finally, in all the above designs, storage devices based on an array of disk 790 may be used instead of semiconductor storage devices, especially if the number of streams supported is not very large. The small semiconductor buffer 795 prefetches the video section currently being accessed by the active video stream. This prefetch can be scheduled exactly. This is because access to video data is exclusively sequential. For the rest of the system, the buffer appears to be the complete source of all video content. FIG. 14 shows this approach.

In summary, the following items will be disclosed with respect to the configuration of the present invention.

(1) A method of transmitting request data to a request client in a data communication system having a host processor connected to the network having a plurality of clients connected to a plurality of switches and a communication network. A step of storing a plurality of selection data in at least one selection switch, a step of transmitting a request message for transmitting the request data to the request client from the request client to the host processor, and the request data. When is a part of the selection data, a control message indicating a request for transmitting the request data to the request client is transmitted from the host processor to the selection switch that stores the request data, and the selection switch causes the selection switch. In response to the control message, the step of transmitting the request data stored in the switch to the request client, and if the request is not a part of the selection data, the request data is transmitted from the host processor to the request. A method that includes steps to transmit to the client. (2) The method according to (1) above, wherein the selection data is stored in the selection switch as a preprocessed packet before transmission of the request message from the request client. (3) The method according to (2) above, wherein each of the preprocessed packets includes a payload from the selected data and a header and trailer of the network protocol stack. (4) A device for transmitting request data to a request client in a data communication system having a host processor connected to the network having a plurality of switches and a plurality of clients connected to the communication network, and a plurality of selections. Means for storing data in at least one selection switch, means for transmitting a request message for transmitting the request data to the request client from the request client to the host processor, and the request data being the selection. In the case of a part of the data, a control message indicating a request for transmitting the request data to the request client is transmitted from the host processor to the selection switch that stores the request data, and the selection switch sends the control message. In response to, the means for transmitting the request data stored in the switch to the request client, and if the request is not a part of the selection data, the request data is transmitted from the host processor to the request client. Means and devices including. (5) A communication system having a plurality of switches, a host processor connected to a data communication network, a plurality of clients connected to the data communication network, and means for storing preprocessed video packets. A means of retrieving the requested preprocessed video packet and dispatching it to the requesting client, and a means of providing information lost from the header and trailer of the network protocol stack in the preprocessed packet. The data communication network, including a plurality of switches having. (6) A communication network having a plurality of switches, a host processor connected to the communication network, a plurality of clients connected to the communication network, and a plurality of switches, each of which is preprocessed. A semiconductor storage device that stores the video packets that have been processed, and in response to a control message, dispatch the address in the storage device of each said preprocessed video packet in the video data requested by the control module. A video dispatcher and multiple output adapters, each with a stream control table containing an entry corresponding to each said request client, where each said entry is the header of the network protocol stack in the preprocessed packet. And in those containing information lost from the trailer, each of the output adapters receives the preprocessed packet requested by the video dispatcher from the semiconductor storage device and from the stream control table. A data communication system including the output adapter including means for merging the information with the pre-processed packet and means for transmitting the pre-processed packet requested by the video dispatcher to the requesting client. .. (7) A method of storing video / audio data for supporting a plurality of search modes, which includes a step of storing the video / audio data as a message sequence, and each of the above messages is a part of the video data. And the video, each of which has a plurality of links associated with one of the search modes, each of which is associated with a select operation mode, the link of which is required for the select search mode. The storage method that points to another video / voice message so as to be linked to the message.

【００６５】

INDUSTRIAL APPLICABILITY As described above, according to the present invention, when a client wishes to receive video and multimedia data, a request is sent to a host processor, and then the host sends a control message. Send to the switch that stores the request data. These switches then send the request data to the request client. However, if the request data is not stored on the switch, the data must be transferred directly from the server to the request client. By offloading the video content to a switch on the network in this way, the video content can be efficiently distributed to the requesting client and the overhead associated with the distribution of the video content from the server to the requesting client can be reduced.

[Simple explanation of drawings]

FIG. 1 is a diagram showing a data structure in a file of a UNIX operating system.

FIG. 2 is a diagram showing a state in which data is offloaded to a switch in a network by an environment in which the present invention is implemented and a pointer pointing to offload data held in a host.

FIG. 3 is a diagram showing a preprocessed packet derived from video content.

FIG. 4 shows a shared buffer switch that is modified to store preprocessed packets.

FIG. 5 shows a shared buffer switch modified to store preprocessed packets.

FIG. 6 shows details of a modified shared buffer switch video dispatcher unit.

FIG. 7 shows the format of a control message transmitted from a host processor to a switch.

FIG. 8 is between a client, a switch, and a host processor, including a client-to-host request message, a host-to-switch control message, and a video packet transmitted from switch to client in response to the control message. It is a figure which shows the message flow.

FIG. 9 shows a suitable video memory used in the present invention.

FIG. 10 is a diagram showing a modified output adapter of the present invention.

FIG. 11 shows another embodiment of the present invention using different switches that do not have a shared buffer.

FIG. 12 shows another embodiment of the invention using different switches that do not have a shared buffer.

FIG. 13 shows another method of the present invention that integrates a semiconductor storage device into a switch.

FIG. 14 shows yet another method of the present invention in which a magnetic disk storage device is used instead of a semiconductor storage device.

FIG. 15 shows a frame sequence within a video stream.

16 is a diagram showing a decoding order at the time of forward reproduction of the frame of FIG. 14. FIG.

FIG. 17 is a diagram showing a decoding order when the frame of FIG. 14 is reproduced in the reverse direction.

FIG. 18 is a diagram illustrating a fast forward and fast rewind function of the frame of FIG.

[Explanation of symbols]

6 Request message 8 Control message 10 Host 20 Client 50 ATM Broadband network 60 Switch 61 Input link 100 Serial link 150 Switch output 150 Output link 200, 200'' Input adapter 210, 260 microprocessor 286, 420, 720, 820 multiplexer 287 Control signal 288 Output link interface logic 288, 870, 871 Interface logic 300 Input bus 310 Output address bus 315, 581 Signal line 315, 761 Control bit 350 Output bus 400 Shared memory 410 Delay element 500 Control section 500, 500'Center Controller 510 Free Cell List 510, 520 FIFA Queue 520 Address Queue 530 Write Address Bus 540 Read Address Bus 581 Request Acceptance Signal 585 Write Permission Signal 600 Control Point 600'General Purpose Computer 700 Video Memory 710 Dynamic Random -Access memory module 717 signal 730 Control Logic 750 DRAM Controller 760 Load Address Bus 790 Disk 795 Semiconductor Buffer 800 Video Dispatcher 810 Tag Memory 815 Scheduler 825 Dispatch Queue 826 Output Adapter Address Field 827 Stream ID Field 828 Video Memory Address Field 850 Cell Address Monitor 855 Incremental Device 900 Video Content 915 Loadage 920 Video Message 925 Pointer 926 Network Switch Address 926 Switch Address Element 927 Message Address 930 ATM Cell 931 Convergence Sublayer Trailer 935 Header 940 Link Field 941 Forward Link 942 Reverse Link 943, 944, 945, 946 Link 950 Flow Control Field 1000 Switch Hardware 1150 Control Circuit 1250 Output Queue 1600 Video Memory Manager

[Reference]

[1] Craig Partridge, "Gigabit Networking", Addison Wesley Publishing Co., Reading, Mass.01867, ISBN 0-201-56333-9, Oct.1993. [2] MJ Bach, "The design of the Unix operating system" ", Prentice Hall Inc., Englewoods Cliffs, NJ, 07632, ISBN 0-13-201799-7 025, 1986. [3] HM Vin and PV Rangan," Designing a multiuser HDTV storage server ", IEEE Jour. On Selected Areas in Communications, 11 (1), Jan. 1993, pp. 153-164. [4] D. Kandlur, MS Chen, and ZY Shae, "Design of multimedia storage server", In IS & T / SPIE symposium on Electronic Imaging Science and Technology, (San Jose, CA 1994). [5] A. Dan and D. Sitaram, "Buffer management policy for an on-demand video" server ", IBM Research Report RC 19347. [6] A. Dan and D. Sitaram," Scheduling policy for an on-demand video server with batching ", IBM Research Report RC 19381. [7] R. Haskin," The Shark continuous media file server ", Proc. IEEE COMPCON 1993 (San Francisco CA, 1993). [8] W. Rosenberry et.al., "Understanding DCE", O'Reilley and Associates Inc., 103 Morris Street, Suite A, Sebastopol, CA 95472, ISBN 1-56592-005-8, Sept. 1992.

Continuation of front page (51) Int.Cl.⁶ Identification Code Agency Reference Number FI Technical Display H04N 5/93 7/173 (72) Inventor Manojay Kumar United States 10598, Yorktown Heights, NY, Overlook Comons 2 H