Quality of service improvement of internet real-time media transmission by transmitting redundant voice/media frames

Improvement of real-time media transmission service quality on the Internet through the transmission of redundant audio/media information frames

<u>Field of invention</u>

The present invention relates to the field of real-time data/sound/media transmission on the Internet, corporate intranet, wired, and any other types of packet switching networks. In particular, the present invention relates to a method for improving the quality of real-time packet transmission by using redundant transmission of packets.

<u>Background of the invention</u>

Internet technology and Internet media transmission have huge business opportunities, and many important industrial players and major telecommunications companies have flooded into this field. Many companies market Internet phone interrogators and Internet phone PC software. The company provides low-cost Internet telephony services for long-distance calls, and telecommunications companies regard Internet telephony as a way to unify telephone and data organization structures.

Internet media transmission includes using special application software to send media packets (including any of the following Projects: n-dimensional images, animation, music, text, movies, video transmission, still images, sound, data, etc.). Internet telephony is a special version of Internet media in which packets contain audio information (sometimes video information). When the sound processed by an input device is captured on a source computer, an application program running on the source computer converts the continuous sound analog signal into a series of discrete digital compressed packets. There are some well-known industry standards that can be used to define this conversion process and these discrete (usually digitally compressed) packet formats, such as pulse symbol modulation (PCM), pan-European digital system (GSM), G.723, etc.

There are other known processes defined by standards (for example, Internet Protocol (IP), User Graphics Protocol (UDP), and Real-Time Protocol (RTP) protocols). Enlarge the packet with the necessary header and trailer , So that these packets can travel to a destination computer on a common packet-switched network. Usually, packets travel on these header and tail columns independently of the packet switching network. (See US Patent No. 5,371,852, Applicant Attanasio et al., published on December 6, 1994, incorporated herein for complete reference). At the destination computer, the arriving packets are stored in a buffer, and then converted back to a form close to the original analog signal. The same industry standards (for example, Pulse Symbol Modulation (PCM), Pan-European Digital System (GSM) G.723, etc.) are used to define this conversion.

Some previous techniques have been revealed: copy messages and transmit them on the "multiple unconnected paths" of a network topology to improve the reliability and timely delivery of these messages. See "Using a multi-repeated book to deliver time-critical messages", by P. Ramanathan and KG Shin, Association for Computer Systems (ACM) Change, Volume 10, No. 2, May 1992 , (Hereinafter referred to as "Shin Reference") are incorporated here for complete reference.

Problem statement using previous techniques

Quality is a serious problem in transmission media on packet-switched networks including the Internet and corporate intranets. This problem comes from two general characteristics of packet-switched networks, namely: (A) packet-switched networks cannot guarantee the delivery of packets, for example, a packet may be lost on the way to the destination, and (B) packet-switched networks cannot guarantee Packet delivery within a given time, for example, if the network is congested, the packet will be delayed within the network.

These two characteristics come from the fact that a packet-switched network contains commonly used paths and links that connect them. Since these resources are shared by many packets, a waiting queue of these resources is built into the network. When the network is congested, the packets are forced to wait in these queues. When the traffic volume exceeds the capacity of these storage columns, packets can be discarded. These are the characteristics of packet-switched networks, so on packet-switched networks, packet transmission cannot avoid packet delay and loss.

TCP (Transmission Control Protocol) remedies some of these shortcomings of the packet switching network by introducing a packet retransmission mechanism between the source and destination computers outside the network. It arranges a buffer inside to store all Packet received. If some packets do not arrive within a given time, these packets are required to be retransmitted. Until all packets are received, the received data will not be released to the receiving application due to potential multiple retries. Therefore, the Transmission Control Protocol (TCP) guarantees that all packets arrive, but the transmission time will be sacrificed, that is, it will be delayed. Because of the delay caused by this automatic retransmission, the Transmission Control Protocol (TCP) is not used for necessarily delayed Internet media transmission.

For two-way Internet media transmission, there must be a long delay. When accepting some lost packets, the Internet media usually uses a protocol (for example, UDP or user graphics protocol) that does not have a built-in packet retransmission. Even with this protocol, some packets may still be lost in the network, and there is no guarantee of a minimum time (no delay) for transmission on the network. Generally, the upper-level application software controls the size of a waiting buffer and the maximum waiting time for packets to arrive.

1. The previous technical system was described in the "Second Anniversary Internet Phone Rush" from July 14 to 15, 1997. It is incorporated here for reference. In particular, "Motorola Internet Protocol (IP) Phone in the Company's Intranet" describes an example of packet delay and loss in Internet media transmission. Here, a series of packets are sent from a source computer to a destination computer on the Internet for a certain period of time. This article shows a graph of the arrival delay of each packet. In the graph, the X axis corresponds to the packets from the first to the last. The Y-axis shows the time required for the packet to travel to the destination. The unit of the Y-axis is milliseconds. The graph shows that the Internet using previous technologies to transmit Internet media is not as reliable as using the telephone network.

The current state of a document comparing Internet/Intranet transmission techniques and transmission on the telephone network is as follows. Compared to telephone networks that provide acceptable sound for more than 99.999% of the time of use, the Internet only provides acceptable sound for 61% of the time of use. (See the article by Tom Nolle, General Manager of CIMI: The title "Convergence 2000?" was published in "Information Week", April 15, 1998, page 141, incorporated here for complete reference).

An example of a typical prior art network system 100 for transmitting media information including audio data is shown as a block diagram in FIG. 1. The network system 100 includes a plurality of computers 160, which are connected to one or more networks 130 through network connectors such as modems and/or local area network (LAN) adapters 150. Usually the computer 160 can be a personal computer (similar to an IBM ThinkPad) or a workstation (similar to an IBM ThinkPad). AS400) and any commonly known computer system. For one-way communication, one computer 160 will be the source computer 160S that initiates information transmission, and one or more computers 160 will be the destination computer 160D that receives the information. However, in many applications, the functions of both the source computer 1605 and the destination computer 160D are included in a single computer such as 160, which can perform these two communication functions, that is, transmission and reception, so that it can be point-to-point two-way, one To many, and/or many to many communication. The computer 160 will have well-known input and output devices, such as a microphone 131, a speaker 132, a keyboard, a mouse, a camera, a video recorder, a screen, a recorder, a musical instrument, a light pen input, a touch screen (not shown), etc. The combination of one or more multimedia interfaces 133 such as a sound card and/or video card 133, network interface software 134, and one or more network connections 150 converts the signal from an analog continuous form 135 to a digital (and usually For compression) Sealed form 120. Through the network connector 150, the packet is exchanged on the network 130 between the computers 160.

The network 130 can be any type of packet switching network, including but not limited to the Internet, corporate intranet, external network, wide area network (WAN), local area network (LAN), telephone network, and /Or any combination or interconnection of such networks. These networks usually include access points 140, routers 110, and network links (usually 175). The network link 175 connects these routers 110 and the access point 140 to form the network shown by the button 130. These routers 110, access points 140, and network links 175 are usually operated by one or more Internet Service Providers (ISPs). The access point 140 is connected to a gateway in the world outside the network 130. Various computers 160 can access the network 130 through the access point 140 through well-known connections including broadcast connections, dedicated line connections, wired connections, satellite connections, and other well-known connections. The access point 140 can be operated by other Internet Service Providers (ISPs) at the same time, and can be connected to a gateway of other networks.

Known standard protocols (Internet Protocol (IP), Point-to-Point Protocol (PPP), Local Area Network (LAN) Protocol), etc. Support various computers 160 for use between the network connector 150 and the access point 140 The connections are independent of each other and exchange data and information. In particular, the user graphics protocol (UDP) and the real-time protocol (RTP) provide a way for computers to exchange real-time Internet media packets on the network 130.

The connection between a series of routers and access points (that is, link 175) used by the packet to travel to the destination is called a "path". The packet switching network 130 and the user graphics protocol (UDP) and real-time protocol (RTP) of the protocol link are very famous. For more descriptions of these networks and protocols, see the example Transmission Control Protocol (TCP)/Internet Protocol (IP), Volumes 1 &amp; 2, Professional Computing Series by W. Richart Stevens, Addison-Ersley, 1994 , Merged here for complete reference. In this disclosure, these packet-switched networks 130 will be referred to as networks 130 without loss of generality.

"Shin Reference" discussion: Use redundancy to reduce packet delivery delay. However, in this reference, hypothetical networks such as C-curled hexagonal meshes and hypercube meshes are used, in which the same subtypes are repeated in the entire network. Using this assumption, it is possible to mathematically define the unconnected path between the two end points. However, in a real network environment, the connection of the router is ad hoc. The network is composed of inherited sub-networks and many branches. Under these conditions, the unconnected path may be calculated in advance with mathematics. "Shin Reference" also assumes that a duplicate packet is sent on each calculated unconnected path. This may cause a serious damage to network resources.

Invention goal

One object of the present invention is a system and method for providing more reliable end-to-end Internet media transmission between two or more points, which are switched through one or more packet-switching networks And connect.

One objective of the present invention is a general method for improving the reliability of end-to-end Internet media transmission.

One object of the present invention is a system and method for a source computer, a destination computer, and a reflection router to negotiate and determine one or more multimedia transmission paths to improve transmission reliability.

One objective of the present invention is a system and method for introducing redundancy in media packet transmission to improve quality, reliability, and transmission delay.

One object of the present invention is a system and method for copying and unifying packets at both ends of a transmission path as an interface with software. The software system is established for non-redundant media packet transmission.

One objective of the present invention is an improved system and method for packet-switched network communication, which improves reliability and reduces delay in packet transmission.

Summary of the invention

The present invention improves the reliability and reduces the delay and packet loss in Internet media transmission such as the packet switching network of the Internet and the corporate intranet. The present invention copies a message/information packet sent from one or more source computers into one or more copies of one or more packets of the sent message. The one or more source computers are connected to the network. Each copy is then directed to one or more destination computers through a different path through the network. In a preferred embodiment, replication and path guidance are performed randomly, and each path is determined so that the path has the least number of routers and access points in common. Since the duplicates are redundant, the loss and delay of some duplicates are not originally intended for the destination to assemble the packet sequence. Therefore, the destination computer can assemble the sent message/information packet from the received copy in a more complete and faster way. The received redundant copy can be ignored and/or discarded at the destination computer.

Detailed description of the invention

2A is a block diagram of the present invention, which is included in a general packet switching network environment. The elements in FIG. 2A are the same as those with the same numerals and descriptions in FIG. 1.

One or more computers 260 and one or more reflection routers 270 included in the system 200 are connected to the network 130 through the access point 140. Communication between two or more computers 260 occurs by sending one or more packets 120 of messages/information from two or more paths (eg 275A, 275B, usually 275) through the network 130. This is accomplished by copying one or more packets 120 in various ways as described below, and sending the copies 120R on different paths 275. In Figure 2A, two paths are shown, path A (275A) and path B (275B). The packet 120 is created, transmitted, and received using well-known techniques. The reflection router 270 is a computer used to separate the paths from each other as described later. The reflective router 270 can become an intermediate router in certain paths.

The computer 260 may be a source computer 260S that sends one or more messages/information, or a destination computer 260D that receives one or more messages/information. Of course, in two-way communication, the functions of the source 2605 and destination 260D computers exist on two or more computers that communicate. Therefore, the components of the computers 2605 and 260D can be packaged into a single computer 260, and these settings can be used interchangeably without loss of generality. An example of Figure 2A is an enterprise intranet.

In an alternative preferred embodiment shown in Figure 2A, the access point 280 with enhanced redundant media transmission (Figures 9 and 10 below) enables prior art computers that do not have the functions of the present invention to connect to these The access point 280 is enhanced to obtain the benefits of redundant media transmission. In this configuration, the copying and unification of packets will be performed in the enhanced access point 280. To simplify the explanation, we will first discuss the details of the combination of a source computer 260S (260), a destination computer 260D (260), and a reflection router 270 in the present invention. Next, the redundant media transmission with the child access point 280 will be explained.

FIG. 2B is a block diagram showing the situation where the network includes multiple Internet Service Provider (ISP) networks connected by the network access point 290. As shown in the figure, the source computer 2605, the destination computer 260D, and the reflection router 270 can be configured in a manner similar to the situation in FIG. 2A. An example of Figure 2B is that a source computer accesses an Internet service provider (ISP X), and the destination computer accesses a different Internet service provider (ISP Y).

3 is a block diagram of a typical source computer 260S or destination computer 260D (or computer 260) used in the present invention. In a preferred embodiment, the computer 260 is used for two-way communication. The computer includes any standard well-known media (for example, audio or video) and/or media interface 133, a standard well-known network interface software 134, and a standard well-known network connector 150, the combination of which can be used to input the media interface Packetize, and transmit the packet to the person 150 connected to the computer 260 according to a protocol suitable for the network 130. The computer further includes one or more known memories 262, a unique initialization process 700, a unique copy process 500, and/or a unique unified process 600. The initiation process 700 selects an alternative path to transmit the copy 1208, the copy process 500 executes the function of creating the source computer 2605 of the copy 120R in various alternative ways, and the unified process 600 executes the unified received copy 120R, and recreates the original at the destination The destination computer function of the sent message. The memory 262 is used to retain the results of the handshake, and will be used for reference to 500 and 600 later. These processes will be described in further detail below.

FIG. 4 is a block diagram showing a more detailed relationship between the packet copy processing 500, the packet unification processing 600, and the packet reflection performed by the reflection router 270.

In a preferred embodiment, the copy processing 500 of the media package takes place in the source computer 260S, for example, each path (such as alternative 275A, 275B, and 275C) creates a copy 120R. (An alternative preferred embodiment of the copy processing 500 is explained below). The copied packet 1208 is sent to the access point 140 through a network connector 150, where it is input to the packet switching network 130. If possible, exotic techniques are used. For example, a preferred embodiment selects different paths (275A, 275B, 275C) for the reflection router 270 for separate packet copies (1208). Therefore, these copies 120R travel through different routers 110 and different network links 175 to reach the same destination computer 260D on different paths (for example, 275A, 275B, and 275C).

In a preferred embodiment, the unified processing 600 of the copy 1208 takes place in one or more destination computers 260D. When the copy 1208 is received, the message/information sent by the unified processing is assembled. In a preferred embodiment, the first received copy 1208 is used to compose the received message, and the later received copy 120R is discarded. Although the copy 120R that fails to reach the destination through one or more paths 275 cannot be used to recreate the sent message on the destination computer 260D, the same copy 120R still has a path through one or more other paths 275. The opportunity to reach the destination computer 260D can therefore be used to recreate the sent message. In this way, the speed and reliability of information/information communication can be improved.

The reflection router 270 is used to reduce the number of routers and network links common to each path (275A, 275B275C). In a preferred embodiment of the handshake process 700, the reflection router 270 is carefully selected by the source computer 260S.

The effectiveness of reflection routers can be explained by analogy to the organizational structure of a post office. Letters and packages correspond to packets, mailboxes correspond to access points, post offices in the middle correspond to routers, and delivery trajectories correspond to network links. Sometimes, mail may be delayed or lost. Using the present invention to minimize the chance of loss or reduce unexpected delay, the mail will be copied with the same destination mark and delivered repeatedly. If the repeated fragments of the mail are carried by different tracks and processed by different post offices, the risk of not receiving (at least one) mail at the destination will be reduced.

Using this analogy, the role of reflection router/server 270 can be explained as follows. If repeated letters are sent from a mailbox with the same address mark, the risk of loss/delay is not similarly reduced, but similar to these repeated letters traveling on the same track and passing through the same post office. In order to further reduce the risk of loss/delay, the sender negotiates with his friend as the reflection router. In this example, two friends A and B are selected as intermediaries before mailing three copied letters. Due to these agreements, the address marks of A and B are placed on the two duplicate letters respectively. Because different locations have different address tags, the three copies will travel to different destinations. Of course, when receiving the copy, friends A and B will replace their address tags with their final destinations. In addition, the copy should be placed in the nearest mailbox closest to each friend for forwarding to the final destination.

Therefore, in a preferred embodiment, the reflection router 270 is used to ensure that each copy 120R travels on a different path 175, so as to reduce the risk of packet loss and accidental delay of packets lower than the intermediate router. In a more preferred embodiment (see below), the source 260S can be used to optimize the selection of paths (275A and B). In Figure 4, each packet (packet 1, 2, 3, and 4) is copied three times to become a set of duplicates 120R (replicas a, b, and c). All the copies 120R marked "a" go to a first reflection router, and finally reach the destination 260D through the path 275A. All the copies 1208 marked "b" travel on the route 275B to the destination 260D, and all the copies 120R marked "c" travel on the route 275C to the destination 260D.

After receiving the copy 1208, 600 assembles the received copy 120R in a unified process to recreate the sent message. The reconstruction will be accomplished by using the well-known packet sequence number information in the header of the real-time protocol (RTP) used to identify the location of each copy in the sent message.

In a preferred embodiment, the destination computer 260D uses the first copy 1208, which is a copy of each given packet 120 in the packet group containing the sent message. The destination computer 260D retains and uses the first received copy 120R to recreate the sent message, and then discards all the later received copies 120R in the packet group that copied the used copy 120R.

The reserved copy 1208 is stored in the buffer array M610, and is used (below) to digest packets that may be out of order before being released to the media (such as audio or video) and/or the multimedia interface 133. That is to say, some reserved copies of 120R may be received in a different order from the message sent. When the copy 120R is received, the reserved ones are placed in the correct order as determined by the packet sequence number information in the header (sent messages). Space is reserved in the buffer array M610 for the unreceived copies in the sequence. Therefore, only when these "late" copies are received, they are placed in the storage location and in accordance with the proper order of the sent messages. A preferred implementation In the example, the buffer array M610 has enough locations for a sequence of 10 received and reserved replicas 1208.

Figure 5A shows details of an alternative preferred embodiment of the replication process 500. When controlling the total number of increased packet transmissions in the network 130, this embodiment enhances the benefits of enhanced reliability in communication. Without using this specific embodiment, the total number of packet transmissions for the redundancy of 2 paths in the network 130 will be twice, and the redundancy of 3 paths will be three times, etc. For example, this specific embodiment enables us to use 3-path redundancy on the network 130 only in 30% (or any other optional) increments of the total number of packets transmitted. In this specific embodiment, some packets 120 will be copied more in a random manner than other packets. A further specific embodiment randomly selects the path 275 for transmitting the duplicate packet 120R.

A preferred embodiment of this process 500 is derived from two external numbers given as parameters from the application. The first number is an integer N, which is used to set the number of paths 275, and the copy 120R of each given packet 120 is transmitted on the path 275 on the network 130. (The selection of different paths for communication with the copy 120R will be further described in Figure 7 below). Fig. 5A shows an example situation in which there are three selected different paths 275, which is the case of N=3. The second number is a rational number T, between 0 and N (the number of paths 275A, B, and C), and is used to set the increment of the target transmission quantity. It is necessary to control the usage of network 130 resources caused by duplication.

With the concept of "redundant packet transmission", there is a leverage relationship between path guidance redundancy and media transmission quality-the more redundancy, the higher the quality, but more network resources are used. The introduction of T allows to increase the route guidance redundancy, but will not increase the total number of packets 1208 transmitted in the network 130 to the degree of route redundancy. As mentioned above, the combination of N=3 and T=1.3 can provide good quality media transmission by only increasing 30% of the traffic on the network and using three paths.

FIG. 5B shows a preferred process 510 for implementing a strategy for generating a copy 1208 a random number one. A rational number T selected like 2.7 has a fractional part (0.7) and an integer part (2). The number of created copies 120R is controlled by the integer part, for example, only an integer number of copies such as 2 copies or 3 copies can be created. In this process, the fractional part of T determines the percentage of packets copied, and the integer part of T determines the number of times to copy. That is, if the target of the average copy is set to 2.7, the preferred processing 510 learns the target of 2.7. In this example, a packet with a probability of 0.7 will be copied 3 times, and a probability of 0.3 will be copied 2 times. The random number "R" is used to know this possibility.

In particular, in step 512, a random number R between 0 and I is generated. In step 514, the random number (R) is compared with the fractional part of T. This fractional part is obtained by taking the difference between the "floor" values of T and T. "Floor(T)" is the value of T truncated the decimal part, that is, the integer part of T. For example: if T=5.1, then Floor(T)=5, and if T=2.9, then Floor(T)=2.

By using a random number in this way, the processing 510 controls the average number of copies 120R copied from the packet based on the target set in "T", and then controls the additional number of network devices required.

In step 512, for any given packet 120, a random number R between 0 and 1 is generated. Step 514 determines whether R is less than the fractional part of T. In particular, R&lt;=T-floor(T). If it is true, perform step 518. If step 516 is performed, the number of times to copy the packet 120 is more than that performed in step 516. Here, the number of copies is an integer value related to T (that is, floor(T)), especially floor(T)+1. On the other hand, if R&gt;T-floor(T), then step 516 is executed, and fewer copies or no copies are generated. The number of replicas here is also related to floor(T), in particular, they are equal.

An alternative equivalent method of controlling the average number of duplicates 120R copied will be faster by the present invention.

The process 520 of FIG. 5C adds a further enhancement of the present invention. Here, each copy 1208 communicates on N paths in a random manner. (Note: When the copy 1208 of this packet can communicate on different selected paths, the original packet 120 can be sent from the source 260S to the destination 260D without using the present invention. On the other hand, in this disclosure, the original packet 120 is usually Called and treated as a copy 1208 without loss of generality).

In step 522, the value of "r" represents the number of copies 1208 of a given packet 120 created by any of the above processes. In step 524, r paths are selected from the set of N selected different paths. This selection is done randomly, so that the copies associated with any given packet 120 are randomly distributed across all paths 275 that must be communicated on the network 130. Note that if r=N, you do not need to select, and each copy 1208 communicates with one of the N paths 275.

In step 524, when r is less than N, the number of copies 1208 is used to select r paths from N available paths 275. For example, if there are 2 copies of 120R (including the original packet 120), and there are 3 different selected paths (275A, 275B, and 275C), then there are (satisfy 3 select 2)₃C₂=3 ways to transmit these two copies of 120R. Step 520 enumerate all_NC_rWay, that is, combine {Ej} and use a random number to select_NC_rOne of the ways. Therefore, in this example, it is possible to avoid more than two copies traveling on the same route. Again, here N is the number of paths, and r is the number of copies.

In step 526, each copy 120R is marked with the address of one of the respective paths selected in step 524. For example, each copy 120R is sent to a separate reflection router 270 related to one of the paths in {Ej}. In an alternative preferred embodiment, N-1 addresses (copy 1208) are sent to the reflection router 270 associated with one of the selected paths, and the address of the destination computer is given to the original packet 120.

FIG. 6A is a flowchart of a preferred unified packet processing 600 performed by a destination host 260D in a preferred implementation of the present invention.

The buffer array 610M has L elements (m[1],...m[L)) for adjusting out-of-sequence packets. In a preferred embodiment, L=10 or less is sufficient. Step 620 initiates the process 600. This initialization system is executed only once before the session to initialize the region variable "sc" and the buffer array M. In the initialization, the array content m and a variable "sc" (current sequence) will be set to 0. The variable "sc" is the number of the latest and most recently received copy 120R, and this is the latest (most recent or rightmost) position m of the buffer 610M_LAssociated with this packet.

The process 600 waits for (630) the arrival of the copy 120R. When it arrives, the serial number is read (630) from the real-time protocol (RTP) header and sent to the variable "s". In step 640, "s" is compared with "sc", that is, the number s of the just received copy 120R is compared with the number of the most recent packet sequence sc. The sc is now related to the buffer 61OM (M_L) The rightmost component. If "s&gt;sc", the packet (copy) just received has a number s, which is newer than the latest sequence number sc in the buffer 610M. Therefore, the buffer 610 must move to the right so as to contain the packet sequence "s" of the packet just received. In this case, control passes to step 650. On the other hand, if s&lt;=sc, the newly arrived packet has a number s, which is earlier (older) than the most recent packet stored in the buffer, which represents the memory related to the newly arrived packet in this case The body position is tied to the buffer, or the buffer has moved through. This situation sinks, and control passes to step 670.

For the arriving replica sequence number s less than or equal to "sc" (640), step 670 is executed. In step 670, the position s of the received packet is compared with the position m of the memory in the buffer 610M. If (670)sc-s&gt;=L, all memory locations m of the buffer 610M have passed (greater than) the location s in the newly created message. Therefore, the newly received packet (copy 120R) is discarded (671), and control is passed back to step 630. However, if sc-s&lt;L in step 670, the newly received packet (copy 120R) has a number s, which is related to one of the memories m in the buffer 610M, and step 672 determines whether the relevant memory location is A value already exists, for example, step 672 checks whether m[L-Sc+s]&gt;=a. If there is a value in the position m[L-sc+s], then a copy 120R with this number s has been received, and the packet information has been stored in the buffer 610M for rebuilding the message. Therefore, the newly received packet (copy 1208) is discarded (673), and control is passed back to step 630. However, if there is no value in the relevant memory location, for example, if the location m[L-sc+s]=0, go to step 674 to fill the buffer with the information of the newly received packet (copy 120R) 610M position m[L-sc+s], that is, if the copy is the first one of the serial number and is still within the buffer (not too late), the buffer content is updated (674). In all these cases, the offset of the buffer and the update of "sc" did not occur.

FIG. 6B shows the buffer 610M in two possible cases of shifting the buffer 610 to the right, and the shift may occur during the execution of step 650. The two cases are shown by the relationship of the packet sequence number. The buffer before the offset is not shaded (in case a, position 18-21, in case b, position 22-25), and after the offset, it is shaded (case a In position 24-27, in case b, position 24-27). In case (a), the arriving replica with sequence number 27 shifts the buffer further by more than L=4 positions (that is, 27-21=6 positions). In case (a), the m memory positions covered in the old position of the buffer 610M do not have any overlap with the m memory positions in the new position of the buffer 610M. In case (b), the newly arrived copy shifts the buffer moderately (27-25=2 positions). In case (b), some memory positions (24 and 25) in the old buffer position overlap with some memory positions (24 and 25) in the new position of the buffer 610M.

These two situations cover all the possibilities of the actions required for the buffer offset, step 660. In case (a), the latest (highest or rightmost memory location m) packet sequence number (sc) has a value of 21 and arrives before the copy of packet #27. In case (b), sc is set to 25. Then receive a copy with a serial number s=27. Since the sequence number is greater than sc in both cases (step 640), the application processing 650 process 650 is recursed to all memory locations, starting at the first memory location m1 in the buffer 610M, until received by the newly arrived copy 1208 One memory before the position. In other words, index-i, recursively from sc-L+1 to s-1.

In particular, if the buffer is shifted to the right (660), the process 650 handles possible situations. Case 1 includes the memory (packet) location that does not exist in the old buffer (before the offset) but exists in the new offset buffer (after the offset). For example, positions 18 to 21 in case (a) and 2223 in case (b) are included in case 1. In case 1, the buffer 610M is offset so that it does not include these positions, and the information in these positions is transmitted to the destination computer to output 133 (656).

Case 2 includes memory (packet) locations that are neither in the old buffer (before offset) nor in the new offset buffer (after offset). These memory locations fall into the "gap" and are shown as locations 22 and 23 in case (a). These packets are regarded as "packets lost" (658), because none of the copies of these packets arrive within the time limit (L), that is, before any related packets/copy 1208 arrives at the destination computer 260D, the buffer 610M Has passed its memory location. Step 658 displays a "zero" output for these missing packets.

Case 33 includes the memory (packet) position m that exists in the old buffer (before the offset) and at the same time exists in the new offset buffer (after the offset). The positions 24 and 25 in case (b) are included in the "overlapping" position in case 3. Therefore, in case 3, the one reserved in a memory location of the old buffer memory will be stored in a memory location of the new buffer. But the position m of this memory position in the buffer will change. Step 655 executes this "left shift" by setting m[i-s+Li=m[i-sc+L] of each memory location in case 3.

Case 4 includes the memory (packet) location that does not exist in the old buffer (before the offset) but exists in the new offset buffer (after the offset). Memory positions 24 to 26 in case (a) and 26 in case (b) are included in case 4. The positions of these packets are created in the new buffer. However, because the packets related to these locations in 610M (within the time limit (L)) have not reached the destination computer 260D, step 657 sets the value of each memory location m[i-s+L]=0.

These conditions are selected for each memory location MI and are recursed by processing 650, especially at the decision points of steps 651-654. Step 651 checks index-i&gt;0. This is not true when the process 650 is initially started, and the buffer is shifted (660) until the entire buffer length L is available for the first received copy 120R. Once the condition in step 651 is false, that is, the entire buffer 610M is available, step 652 determines whether the processed memory location is less than or equal to sc, that is, whether the memory location may exist in the old buffer. If index-i&lt;=sc, it is possible, and step 653 checks whether index-i&gt;sL, that is, whether the memory location falls in the old buffer, then step 655 (case 3), or no, then This is step 656 (case 1). If index-i&gt;sc (step 652), the processing memory location cannot exist in the old buffer, and step 654 determines whether index-i&gt;sL. If 654 is true, the memory location information has not arrived, and it is case 4, go to step 657. If step 654 is false, the memory location falls within the "gap", and step 658 is executed (case 2).

After step 650 is completed by setting m[L]=s and sc=s, step 660 shifts the buffer.

FIG. 7 is a flowchart of a handshake (initial) process 700 performed between the source host/computer and the reflection router/server.

In step 710, the source computer 260S obtains the Internet Protocol (IP) address of the reflection server in the service. These Internet Protocol (IP) addresses are taken from a network directory.

In step 720, the source computer 260S sends a request to all reflection servers 270 (or a subset of reflection servers) to report the connection (link or relay 175) between the respective reflection servers 270 and the destination 260D. Collection). The result will be obtained with the list of routers between the respective reflection server Ri and the destination computer 260D. Each reflective router Ri in this list is called LAi. The standard Internet Protocol (IP) supports a command (tracert) to obtain this list. This requirement is processed by step 820 in FIG. 8 below.

In step 730, the source computer 260S checks the connections between the source computers 260S and all reflection routers (the set of links 175). The result will be LB_i. This can be done with the same "tracert" command, which is part of the Internet Protocol (IP) standard.

In step 740, the corresponding LA and LB are connected in series to create a router list from the source computer 260S through a special reflection router Ri to the destination computer 260D. This list will be called LABi.

In step 750, the {LABi} set of overlapping routers will be checked. Then select N paths 275 so that {LAB_i} Its subset has the least common route3.

Here is a better way to perform step 750:

1. Let S denote a set containing selected routers. The initial setting S={route without reflection router}. Let C denote the path to be selected.

The initial setting C={path corresponding to all available reflection servers}.

2. Use {LAB_i}, the control is included in {LAB_k}(K is a component of S) in the router and calculate LAB_j(j is a component of C) in the common router, and set to P_j. Select the given minimum value P_jOfj. Now j has been selected.

3. Insert "j" into S and remove "j" from C.

4. Repeat from 2 until the size of S is enough. (=N)

5. When 2~4 are over, set S contains the selected reflection server.

In step 760, the source computer 260S requests the N reflection routers, and each selected path 275 requests one to provide services. Therefore, a target destination address will be sent to each replication router 270. The target destination address will be reserved in the address mapping table 810 in the reflection server. Later the reflection server uses this address to forward the copy 120R to the destination 260D. This requirement will be handled by the 830 shown in the reflection router (Figure 8).

In step 770, the respective Internet protocols (IP) of the selected N reflection routers are written into the memory 262, so that the copy processing 500 and the unified processing 600 can use these Internet protocols (IP). The memory 262 will retain the {S} determined by the 750 explained above. The list of hops is queried by issuing the "Tracer" Internet Protocol (IP) command in 820, and the result will be sent back to 260S for the best reflection router list {S} decision. There is no need to keep the hop list in the reflection router. A directory should be outside the reflective router. Usually a domain gatekeeper or domain name server of the Internet Protocol (IP) can perform this task. The domain name server knows, for example, all available servers in the domain.

FIG. 8 is a flowchart of a process 800, which is executed by a preferred reflection router 270. The reflection router 270 includes one or more (in FIG. 2) address mapping tables 810, and four basic steps 820, 830, 840, and 850. The entry in the address mapping table 810 includes a pair of source 260S and destination 260D computers.

The process starts by waiting for an input on the network 805. This input is transmitted from the source 260S or destination 260D computer. In step 808, the type of the input is determined. The input can be: a query of a hop list, a transmission demand, a packet 120R from the source 260S, or a packet 1208 from the destination computer 260D. In the handshake process, the first two types of input go to the reflection router. Each input type is processed by steps 820, 830, 840, or 850, respectively.

If the input 805 comes from a source computer 260S as a query for a hop list from the special reflection router 270 to the destination 260D, step 820 is executed. Step 820 returns a hop list (or a part of a potential path 275) between the special reflection route 270 and the destination. This step 820 is explained in the explanation of step 720 above.

If the input 805 is a transmission requirement given from a source computer 260, step 830 combines the Internet Protocol (IP) addresses of the source computer 260S and the destination computer 260D into a pair, and adds the address pair To its address mapping table 810. When the communication session ends, the address pair will be removed from the memory 810. The end of the session can be determined in two ways: 1. The source or destination computer informs to hang up, or 2. The reflection router has not detected any activity (suspended) during a long period of time.

If the input 805 is a (media) packet 1208 transmitted from the source computer 2605, as identified by the header information on the packet 1208, step 840 is executed. In step 840, the Internet Protocol (IP) address of the source computer (sender) 260S is used to scan the first element (identify the source computer 260S) of the stored address mapping table 810 pair. Once the address pair including the source computer 260S is found, the packet is re-sent to the destination computer (or computer 260D) in the second component of the found address (identifying the destination 260D related to the source 260S) .

If the input 805 is a (media) packet 120R transmitted from the destination computer 260D, as identified by the header information on the packet 120R, step 850 is executed. In step 850, the Internet Protocol (1P) address of the destination computer 260D is used to scan the second component (identifying the destination computer 260D) of the stored memory 810 pair. Once the address pair including the destination computer 260D is found, the packet 120R is re-sent to the source computer (or computer 260S) in the first component of the found address pair (identifying the source 260S related to the destination 260D) .

FIG. 9 is a block diagram showing an alternative preferred embodiment 900 of the present invention. In this embodiment, the redundant media transmission is generated at one or more network access points. These access points are routers 280 with source and/or destination computer 260 functions, which are combined with reflection router 270 functions. For example, as shown in this illustration, it is possible to embed the copy process 500 and the unified process 600 in the access point 280. The above-mentioned access point 280 with embedded copy processing 500 and/or unified processing 600 is called "network access point with redundant media transmission function" (or just redundant access point, usually 280), It is usually managed by an Internet Service Provider (ISP). In a preferred alternative embodiment, the source and/or destination computer is a standard previous computer 160 that does not have the characteristics of the present invention. Generally, the link (175, 975) between the source and/or destination computer 160 is as short as possible, such as a regional telephone link connection, to minimize the distance between the source/destination computer 160 and the redundant access point 280 Any packet loss or delay. Since the duplication 500 and/or the unified 600 occurs in the Internet Service Provider (ISP) network (at the access point 280), the bandwidth of the broadcast access line between 150 and 140 may be lower.

The benefit of this specific embodiment is: allowing computers with regular Internet media software to obtain the benefits of the present inventions enhanced quality of service (QoS) by virtue of redundancy features, that is, without the need for additional software at the source and/or purpose Work on the local computer. This can happen in several ways. The source computer (160, 960S) can be a standard computer with a connection to a first redundant access point 280-1. At this access point 280-1, the copy 500 of the packet 120 takes place using any of the aforementioned processes. The first redundant access point 280-1 determines how the multiple paths and the replica 120R communicate on the network 130. (Alternatively, the copy 500 is received by a source computer 260S enhanced with the present invention), and the copy 120R is received by a destination computer 260D enhanced with the present invention and processed as described above, or by a The second redundant access point 280-2. If a second redundant access point 280-2 is used, the unified process 600 is executed on the second redundant access point 280-2, and the unified (re-established) message is uploaded to a standard via the short link 975 The previous technology computer 160.

FIG. 10 is a block diagram of a network access point 280 with redundant media transmission function. The access point 280 has a well-known interface 282, in which there are one or more prior art computers. At the same time, it has a well-known hardware and software interface 132, in which there are one or more links 175 of any general network 130 connected to one or more routers 110. Note that the router 110 function can be combined with any redundant access point 280 function. The redundant access point 280 further has any one or more of the following as described above: the initialization process 700, the memory 262, the packet duplication process 500, and/or the packet unification process. As described above, the packet 120 and/or request is received from the computer 160, copied by the copy process 500, and communicated on two or more paths on the network. In a similar manner, the demand and/or copy 1208 is received from the network (130, 110) through the network interface, and unified by the unified packet processing 600 before being sent to the computer 160 as a re-established message.

Given this disclosure, those skilled in the art will understand equivalent specific embodiments. These equivalent specific embodiments are also considered in the present invention.

The first figure is a block diagram of a known prior art packet network system, which is used to transmit media information including audio data.

The second figure A is a block diagram of the present invention, which is included in a general packet switching network environment containing an example Internet Service Provider (ISP) network.

The second diagram B is a block diagram of the present invention, which is included in a general packet-switched network environment with multiple instances of Internet Service Provider (ISP) networks.

The third figure is a block diagram of a typical source/destination host.

The fourth figure is a graph showing the packet copy, packet unification, and packet reflection performed by the three components of a preferred embodiment of the present invention-a source computer, a destination computer, and a reflection router.

Fifth Figure A, Fifth Figure B, and Fifth Figure C are block diagrams respectively showing the packet copy system, a flowchart of the copy processing of an insert, and a flowchart of the path determination processing of an insert, etc. A preferred embodiment.

The sixth figure A is a flowchart of the unified processing of a packet, which is executed by a destination host in a preferred embodiment of the present invention.

The sixth figure B is a figure showing two examples of moving the buffer.

The seventh figure is a flowchart of a handshake process performed between the source host/computer and the reflection router/server.

Figure 8 is a flowchart of the processing performed by a reflection router.

The ninth figure is a block diagram showing the alternative use of a preferred embodiment in a network access point where redundant media transmission has been enabled.

Figure 10 is a block diagram of a network access point with redundant media transmission enabled.