HK1190537B - Effective circuits in packet-switched networks - Google Patents

Description

Efficient circuit in packet switched networks

Technical Field

The present invention relates to packet switched networks, and more particularly to efficient circuits in packet switched networks.

Background

Messages are often transmitted over packet-switched networks using the transmission control protocol/internet protocol (TCP/IP) suite of protocols. TCP/IP uses a trial and error approach to determine the path bandwidth for message transmission by the sender device. The rate at which the sender device sends messages increases until packet loss occurs. TCP/IP detects packet loss by noting that no acknowledgement has been received for a sent message. Packet loss often results from events such as buffer overflows that occur at intermediary or endpoint devices. After detecting packet loss, TCP/IP reduces the transmission rate and transmits messages at progressively higher rates until packet loss is again detected. While this approach works well for the case of large numbers of messages being transmitted between pairs of devices, it is not efficient to transmit small messages or small numbers of messages, as the messages may all be transmitted before TCP/IP has the opportunity to detect packet loss. If the initial rate used is too high, all messages that have been sent may need to be retransmitted.

In addition to retransmissions, packet loss can also result in temporary suspension of message transmission from the sender device. When TCP/IP detects a certain number of packet losses over a period of time, it considers the network as congested and TCP/IP increases the delay between messages transmitted from a sender device experiencing packet losses. Such delays may be far more costly than retransmissions for overall performance. A sender device with sufficient bandwidth to allow many small messages to be transmitted in parallel to many recipients may face a particular risk of transmission suspension when using TCP/IP.

The use of a fully halved bandwidth network may alleviate congestion in the core, but packet loss may still occur at the end stations. If TCP uses loss as a congestion signal, unnecessary retransmission delays may still occur.

Another method for messaging is to set up a circuit between two devices across a network. The circuitry typically involves the allocation of bandwidth to the communication channel between the devices at the devices themselves and at each intermediary device. However, due to the high cost of setting up and tearing down circuits, short messages, which are exemplary of many network applications, may not be a justifiable reason for the cost of circuit setup.

Disclosure of Invention

Sender and receiver devices communicating over a packet switched network establish an effective circuit between themselves by exchanging requests to send messages and providing responses for permission to send the messages. Sufficient bandwidth at the sender device is ensured by limiting the number of messages to be transmitted in parallel, and sufficient bandwidth is reserved at the receiver device in response to the receiver device receiving a request to transmit a message. The packet-switched network between the sender and receiver devices may be a full-bandwidth-halved network or a high-bandwidth-halved network, making it unnecessary to reserve bandwidth at the intermediary device. The receiver device may also be configured to reject the sender request when the received request will utilize more bandwidth than is available to the receiver device. In response to its request being denied, the sender device may select a different message directed to a different recipient device, and may communicate a request to send the message to the different recipient device. By switching to a different message and a different receiver device, the sender device ensures that it is not idle but still has a message to transmit.

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

Drawings

The detailed description is set forth with reference to the drawings, wherein the left-most digit of a reference number identifies the drawing in which the reference number first appears. The use of the same reference numbers in different figures indicates similar or identical items or features.

FIG. 1 illustrates an example environment in accordance with various embodiments.

Fig. 2a-2b illustrate example queues for a sender device, according to various embodiments.

Fig. 3 illustrates an example queue of a recipient device in accordance with various embodiments.

Fig. 4 is a flow diagram illustrating operations performed by a sender device to establish an active circuit with a receiver device over a packet-switched network in accordance with various embodiments.

Fig. 5 is a flow diagram illustrating operations performed by a receiver device to establish an efficient circuit with a sender device over a packet-switched network based on a reservation of bandwidth for the receiver device, in accordance with various embodiments.

FIG. 6 is a block diagram of an example computer system architecture, in accordance with various embodiments.

Detailed Description

Techniques for establishing an efficient circuit between a sender device and a receiver device over a packet-switched network are described herein. As used herein, the term "active circuit" refers to a communication channel between two endpoint devices in which the channel bandwidth is ensured. In contrast to conventional circuits, the efficient circuits discussed herein do not require a significant overhead for setup. By utilizing a packet-switched network that fully or highly bisects bandwidth, bandwidth reservation at the mediation device becomes unnecessary. Bandwidth at the end points of the active circuit is ensured by limiting message delivery at the sender device and reserving bandwidth for messages of the sender device at the receiver device.

The present disclosure makes use of one such observation: in high or fully halved bandwidth networks, congestion occurs entirely at the end stations (sender and receiver devices) and not in the network core. Thus, bandwidth allocation at the network edge becomes feasible compared to conventional methods that observe packet loss (as an implicit signal from the network core).

To conserve receiver device bandwidth, a sender device transmits a Request To Send (RTS) message to a receiver device for each data message that the sender device needs to send. A sender device may have multiple data messages to transmit to one or more receiver devices, and may limit the number of RTS messages sent based on the bandwidth used by the sender device to transmit the data messages. When limiting the number of RTS messages, the sender device may respond negatively to at least some RTS messages and thus request transmission of data messages that would otherwise collectively use a higher bandwidth than is available to the sender device. In some embodiments, a sender device may have multiple data messages to be transmitted to a single receiver device and may send one RTS message for the multiple data messages.

A receiving device may receive RTS messages from multiple transmitting devices. These RTS messages may request permission to send data messages that would otherwise collectively use a higher bandwidth than is available to the receiving device. To ensure that a receiving device receives only as many simultaneous or concurrent data messages it has bandwidth to receive, the receiving device may reserve bandwidth for one or more sending devices to transmit their data messages and respond to their RTS messages with a message that rejects other sending devices' requests to send data messages (these negative responses are referred to herein as "busy retry-later" (BTL) messages). The recipient device responds to the sender device for which bandwidth has been reserved with a message that provides permission (clear) to send data messages (these messages providing permission to send are referred to herein as "CTS" messages). In selecting which sender devices to respond with CTS messages, the receiving device may sort the RTS messages in some manner. For example, the receiver device may order the RTS messages based on a priority included in the RTS message or based on the number of BTL messages previously sent to the sender device of the RTS message.

Upon receiving the CTS message, an active circuit is established between the sender device and the recipient device that received the CTS message. The sender device may then proceed to send the data message to the receiver device for which permission has been received. In some embodiments, a recipient device may respond to a subset of RTS messages sent by a sender device to the recipient device with CTS messages only.

In response to receiving the BTL message, the sender device can select a different data message directed to a different receiver device and send an RTS message for the data message to the receiver device. In some embodiments, the data message may be queued by the sender device, and the sender device may select a first message from the queue that is directed to a different receiver device and for which an RTS has not previously been sent. By reserving bandwidth at an alternative receiver device, the sender device ensures that it does not have spare bandwidth but still has data messages to send.

In some embodiments, the sending device does not have to send an RTS for every data message. A data message that is a control message or a data message that is less than a threshold size may simply be sent to the recipient device without establishing an active circuit. This further reduces the overall overhead of the scheme.

Example Environment

FIG. 1 illustrates an example environment in accordance with various embodiments. As shown in fig. 1, a sender device 102 may communicate with a receiver device 104 over a packet-switched network 106. The sender device 102 may be provided with a network module 108, the network module 108 receiving a message 110 from an application 112 of the sender device 102 to be transmitted to the receiver device 104. The network module 108 may queue the message 110 in the queue 114 of the sending device 102. Prior to transmitting the message 110 to the recipient device 104, the network module 108 may transmit a Request To Send (RTS) message 116 for the message 110 to the recipient device 104 via an interface 118 of the sender device 102. These RTS messages 116 can then be received via an interface 120 of the recipient device 104 and processed by a network module 122 of the recipient device 104. The network module 122 may arrange the RTS message 116 in a queue 124 of the recipient device 104 for ordering the RTS message 116. The receiving device 104 may then respond to the RTS message 116 with a message 126 providing permission to send (i.e., a CTS message) for the message 110 or with a message 126 denying the RTS message 116 (i.e., a BTL message). The sender device 102 receiving the CTS message 126 may then transmit the message 110 to the applications 128 of the recipient device 104, with the message 110 being directed to those applications 128 by the applications 112 of the sender device 102. The sender device 102 that receives the BTL message 126 may select other receiver devices 104.

Although the sender device 102 and the receiver device 104 are illustrated herein as separate and distinct devices, it should be understood that any computing device may be both the sender device 102 of some messages 110 and the receiver device 104 of other messages 110. Such a computing device would then be equipped with the network module 108, application 112, and queue 114 of the sender device 102, and the network module 122, queue 124, and application 128 of the receiver device 104. A computing device configured to be capable of acting as both a sender device 102 and a recipient device 104 may also have a single set of interfaces (in which case interfaces 118 and 120 would refer to the same set of interfaces), or two sets of interfaces (in which case one set (interface 118) may be dedicated to sending messages 110 and the other set (interface 120) may be dedicated to receiving messages 110).

In various embodiments, the sender device 102 and the receiver device 104 may be any type of computing device. For example, the sender device 102 and the receiver device 104 may be or include a Personal Computer (PC), a laptop computer, a server or server farm, a mainframe, a tablet computer, a workstation, a telecommunications device, a Personal Digital Assistant (PDA), a media player, a media center device, a Personal Video Recorder (PVR), a television, or any other type of device or devices. In some implementations, one or more of the sender device 102 and the receiver device 104 represent one or more virtual machines implemented on one or more computing devices. The characteristics and functions of the modules and data of the sender device 102 and the receiver device 102 will be further described herein. An example computing device for implementing one or both of the sender device 102 and the receiver device 104 is illustrated in fig. 6 and will be described in more detail below with reference thereto.

In various implementations, the network 106 may be any one or more types of networks, such as a Wide Area Network (WAN), a Local Area Network (LAN), or the Internet. Moreover, the network 106 may be public, private, or include both public and private networks. Further, the network 106 may be wired, wireless, or include both wired and wireless networks. Network 106 may communicate using any one or more protocols, such as TCP/IP, other packet-based protocols, or other protocols. In one embodiment, network 106 may include a cloud computing environment connecting a plurality of nodes of the cloud computing environment. In such an embodiment, the sender device 102 and the receiver device 104 may be nodes of a cloud computing environment.

As mentioned above, the network 106 may be a packet-switched network. Such a network 106 may also be a fully-halved bandwidth or a highly-halved bandwidth network, allowing any node of the network to communicate with any other node at full speed without any transmission delay introduced by intervening nodes. In other embodiments, the network 106 may be an infiniband network. The network 106 may also include one or more switches. The switches may be any type of switch and may each include network interface components, such as incoming and outgoing network interface components, each having a bandwidth. For example, a switch may have multiple incoming ethernet ports and incoming wireless ports, as well as outgoing ethernet and wireless ports. In some embodiments, the incoming bandwidth of a switch is proportional to the outgoing bandwidth of the switch. For example, the total incoming bandwidth of the network interfaces that serve devices "below" a switch in the network hierarchy may be 10GB per second, while the total bandwidth of the network interface components up to the core switch may also be 10GB per second. By making the incoming bandwidth of the switch proportional to the outgoing bandwidth, bottlenecks associated with the switch are avoided from being introduced. Such switches with proportional bandwidth are described in more detail in united states patent application No.12/410,697 entitled "Data Center with out Structural hubs" filed on 25/3/2009, united states patent application No.12/410,745 entitled "Data Center interconnection and Traffic Engineering" filed on 25/3/2009, and united states patent application No.12/578,608 entitled "Agile Data Center Network Architecture" filed on 14/10/2009.

In some embodiments, as shown in fig. 1, the sender device 102 and the receiver device 104 may each include an application. The sender device 102 may include an application 112 and the receiver device 104 may include an application 128. Applications 112 and 128 may be any type of application capable of reading and writing data, such as data message 110. Applications 112 and 128 may be the same type of application or different types of applications. Moreover, application 112 may represent multiple applications and application 128 may represent a corresponding plurality of applications. The application 112 may be a client, a server, or a peer of the application 128. From the perspective of applications 112 and 128, the exchanged data messages 110 are sent directly without having to know the RTS/CTS message exchange or the active circuitry.

In various embodiments, the data message 110 may include any type of data of any kind and may have any size. Each data message 110 may be packetized into one or more packets for transmission over the network 106 by an application 112, a network module 108, or some other component of the sender device 102, such as a platform or network stack of the sender device 102. The number of packets comprising data message 110 may vary depending on the size of data message 110 and the network protocol used to transmit data message 110. In addition to its data, each data message 110 may also be associated with metadata. Such metadata may include an identification of the recipient device 104 to which the data message 110 is directed, and if the data message 110 is part of a group of data messages 110, the metadata may also include a sequence number identifying the location of the data message 110 within the group.

In some embodiments, the network module 108 may include any one or more modules, applications, processes, threads, or functions. The network module 108 may be a platform of the sender device 102 or a component of a network stack of the sender device 102, or may be independent of other sender device 102 modules and applications. As mentioned above, the network module 108 may be configured to perform at least one of: receiving a data message 110, branching a received data message 110, queuing a data message 110, selecting a data message 110 for transmission, transmitting an RTS message 116 for the selected data message 110, receiving a CTS message 126 or a BTL message 126 in response, transmitting a data message 110 in response to a CTS message 126, or selecting an alternative data message 110 in response to a BTL message 126. In addition to these operations, the network module 108 may also manage the interface 118 of the sender device 102. These interfaces 118 may be selected by the network module 108 for transmission of the RTS message 116 and the data message 110. Moreover, the network module 108 may perform these operations concurrently on any number of data messages 110. For example, the network module 108 may receive a data message 110 from the application 112 while transmitting an RTS message 116 for another data message 110.

In some embodiments, upon receiving the data message 110 from the application 112, the network module 108 may determine whether the data message 110 is a control message or a message having a size less than a threshold value to fork the received data message 110. The network module 108 provides the data message 110 as a control message or less than a threshold to the network stack of the sender device 102 for transmission using the interface 118 of the sender device 102. Data messages 110 that are not control messages and are greater than the threshold are then queued by the network module 108 for subsequent transmission.

In various embodiments, the network module 108 stores the received data message 110 in a queue 114 or queues 114. The sender device 102 may have a single queue 114 in which the data messages 110 for all receiver devices 104 are stored, or may have a queue 114 associated with each receiver device 104. In other embodiments, the sender device 102 may utilize other numbers of queues 114 having other associations with the receiver device 104.

For example, fig. 2a illustrates an example of a queue 114 for storing data messages 110 directed to multiple recipient devices 104. As shown in fig. 2a, a queue 202 (which may be an example of queue 114) includes a plurality of entries 204 for data messages 110. Although these entries 204 are shown as rows of a table, it should be understood that the entries 204 may also be represented as columns or items in some non-tabular form. Each entry 204 includes a message identifier 206, an indicator 208 of whether an RTS message 116 was sent for the data message 110 represented by that entry 204, and an identifier 210 of the intended recipient device 104. Each message identifier 206 may be any type of data value, such as an integer or a string, that uniquely identifies the data message 110. Each indicator 208 may be, for example, one of a finite set of binary values or other value types that indicate whether an RTS message 116 was sent. Each identifier 210 to the intended recipient device 105 may be a network identifier of the recipient device 104, such as an IP address or other form of address.

Fig. 2b illustrates an example of a plurality of queues 114 for storing data messages 110, one queue 114 for each of the plurality of recipient devices 104. As shown in fig. 2b, each of queues 212, 214, and 216 (which may be an example of queue 114) includes one or more entries 204 of data message 110. Although these entries 204 are shown as rows of a table, it should be understood that the entries 204 may equally be represented as columns or items in some non-tabular form. Each entry 204 includes a message identifier 206 and an indicator 208 of whether an RTS message 116 was sent for the data message 110 represented by that entry 204. There need not be a field representing the identifier 210 of the intended recipient device 104 of the data message 110, as each of the queues 212, 214, and 216 is associated with a particular recipient device 104. Each message identifier 206 may be any type of data value, such as an integer or a string, that uniquely identifies the data message 110. Each indicator 208 may be, for example, one of a finite set of binary values or other value types that indicate whether an RTS message 116 was sent.

The queue 114 may be any type of data structure known in the art, including a data structure of a module, such as the network module 108 or other file or database. Also, the queue 114 may be a first-in-first-out (FIFO) data structure as is known in the art, or the data messages 110 may be added to the queue 114 or removed from the queue 114 in a different order. For example, the data message 110 may be added to the end of the queue 114 but may be removed from the queue 114 in a different order. In one such example, the position of the data message 110 in the queue may be one of a number of factors in selecting the data message 110 and removing the data message 110 from the queue 114 for transmission.

In various embodiments, the network module 108 selects one or more data messages 110 from one or more of the queues 114 in response to the data messages 110 being added to the queues 114, in response to a timer estimating the time at which the sender device 102 will complete transmission of other data messages, or in response to input from the platform of the sender device 102. The network module 108 may select the data message 110 from the queue 114 based on one or more factors. These factors may include the location of the data message 110 in the queue 114, from which queue 114 the data message 110 was previously selected, the size of the data message 110, the available bandwidth of the sending device interface 118, the ability to link multiple data messages 110 together for transmission to a single receiving device 104. These factors are provided for illustrative purposes only, and any other number of factors may be used in alternative embodiments.

In some embodiments, the network module 108 first determines the available bandwidth of the sender device interface 118. The available bandwidth may be a preset number known to the network module 108, such as a number representing eighty percent or ninety percent of the total bandwidth of the interface 118. In other embodiments, the available bandwidth may vary and may be determined repeatedly at different times.

The network module 108 may then select as many data messages 110 to be transmitted with the available bandwidth as possible. In one embodiment, the network module 108 selects the data message 110 from the head of the one or more queues 114 without reference to the recipient device 104 until the collective size of the selected data messages 110 approaches the available bandwidth. In other embodiments where the sender device 102 has multiple queues 114 for multiple receiver devices 104, the network module 108 may service the queues in a round robin fashion, selecting the data message 110 from the next queue 114 to service. In other embodiments, rather than selecting multiple data messages 110 for a single recipient device 104, the network module 108 may link the data messages 110 for the single recipient device 104 in order to reduce the number of bandwidth reservations required by the recipient device. In such embodiments, the network module 108 tracks the recipient devices 104 to which the linked data message 110 has been transmitted in order to prevent a single recipient device 104 from dominating the message transmission. In still other embodiments, the network module 108 prioritizes data messages 110 that have previously sent the RTS message 116 and data messages 110 that have exceeded a threshold amount of time. The reason for waiting the threshold amount of time is to allow the recipient device 104 that provided the BTL message 126 to complete its reception of the other data messages 110 and to free up its reserved bandwidth.

In some embodiments, by considering the available bandwidth of the interface 118 when selecting the data messages 110, the network module 108 limits the number of data messages 110 that can be transmitted in parallel in order to avoid transmission bottlenecks on the sender device 102. However, in the event that an RTS message 116 of a plurality of selected data messages 110 can be rejected, the network module 108 may select a greater number of data messages 110 than the available bandwidth for transmission in order to ensure full utilization of the available bandwidth.

In various embodiments, upon selecting a data message 110, the network module 108 generates and transmits an RTS message 116 for the selected data message 110. The network module 108 may generate and transmit an RTS message 116 for each selected data message 110, or may generate and transmit an RTS message 116 for a group of data messages 110 to be transmitted in parallel to a single receiver device 104. The RTS message 116 can be a small message that identifies the particular data message 110 associated therewith, the size or sizes of the one or more data messages 110 associated with the RTS message, an identifier to the intended recipient device 104, and/or a message priority. The message priority may be determined by the network module 108 based on the ratio of data messages 110 queued for the intended recipient device 104 of the RTS message to data messages 110 queued for other recipient devices 104 and the total size of the one or more queues 114. In embodiments where the RTS message 116 is associated with a chain of data messages 110, the RTS message 116 can identify the number of data messages 110 for that recipient device 104.

After generating the RTS message 116, the network module 108 selects one or more available interfaces 118 for transmission of the RTS message 116. Interface 118 may be any type of network interface known in the art, such as a wired or wireless interface for a WAN or LAN, for a PAN orA wireless interface to a network, or any other type of interface. For example, interface 118 may include one or more network cards. These interfaces 118 may include a pool of interfaces managed by the network module 108 or another component as a common resource that shares the same set and state of queues (i.e., queues 114). In one embodiment, the bandwidth of interface 118 may be allocated to different processes, including network module 108The one or more processes of (a). This may include independent use of a single network interface 118 by multiple processes. As long as the processes statically partition the network bandwidth in advance, the processes can use the allocated bandwidth without coordination. Upon selecting one or more available interfaces 118, the network module 108 transmits an RTS message 116 over the one or more available interfaces 118.

In response to sending the RTS message 116, the sending device 102 receives a CTS message 126, a BTL message 126, or both. For each RTS message 116 sent by the sender device 102, a CTS message 126 or a BTL message 126 may be returned thereto.

Upon receiving the CTS message 126 via the interface 118, the network module 108 determines to which data message 110 or data messages 110 the CTS message 126 provides permission. As mentioned above, receipt of the CTS message 126 from the recipient device 104 establishes an active circuit between the sender device 102 and the recipient device 104. The CTS message 126 may identify a particular data message 110 by a message identifier 206 or may refer to a particular RTS message 116, which particular RTS message 116 may in turn be correlated by the network module 108 with a particular data message 110. The CTS message 126 may also identify a plurality of data messages 110 that are permitted to be transmitted to the recipient device 104 that sent the CTS message 126. For example, CTS message 126 may be in response to an RTS message 116 requesting permission to send several data messages 110 to recipient device 104. Such CTS messages 126 may provide transmit permission to one, some, or all of the data messages 110 identified in the RTS message 116.

In various embodiments, upon determining the data message 110 identified by the CTS message 126, the network module 108 may select one or more of the interfaces 118 for transmitting the data message 110 and transmit the data message 110 via the selected interface 118. In one embodiment, the interface 118 for transmitting the data message 110 may be different from the interface 118 for transmitting the RTS message 116 for that data message 110. After transmitting the data message 110, the network module 108 may remove the data message 110 from the one or more queues 114.

In addition to or in lieu of receiving one or more CTS messages 126, sender device 102 may receive one or more BTL messages 126 via interface 118. Upon receiving the BTL message 126, the network module 108 determines which data message 110 or data messages 110 were rejected by the BTL message 126. The network module 108 may then update the indicators 208 for those data messages 110 in the queue 114 to reflect that the RTS message 116 for those data messages 110 has been rejected.

The network module 108 may then proceed to select one or more alternative data messages 110 for transmission in place of the rejected data message 110. In some embodiments, in selecting the alternative data message 110, the network module 108 may utilize the above-described factors for selecting the now-rejected data message 110. In selecting one or more alternative data messages 110, the network module 108 may also consider the size of the rejected data message 110 or the common size of the plurality of rejected data messages 110. Also, in selecting one or more alternative messages, the network module 108 can filter out data messages 110 for which the RTS message 116 has been rejected and data messages 110 directed to the recipient device 104 from which the BTL message 126 was received. Once an alternative data message 110 is selected, the network module 108 generates an RTS message 116 for the alternative data message 110, selects an interface 118 for use in transmitting the RTS message 116, and transmits the RTS message 116. By selecting the alternative data message 110 instead of waiting to transmit the previously selected data message 110, the network module 108 ensures that the sender device 102 is not idle but still has data messages 110 waiting to be transmitted.

In some embodiments, as mentioned above, the sender device 102 may utilize a timer to determine when to select other data messages 110 for transmission. The timer may be part of the network module 108 or a separate component. The timer is initiated either when the data message 110 is selected or when transmission of the data message 110 begins, and the timer estimates the time for transmitting the data message 110 based on the available bandwidth and the size of the data message 110. Once the estimated time is reached, the timer notifies the network module 108 that the time has been reached to enable the network module 108 to select other data messages 110 for transmission.

In various embodiments, the network module 116 may include any one or more modules, applications, processes, threads, or functions. The network module 116 may be a platform of the recipient device 104 or a component of a network stack of the recipient device 104, or may be independent of other recipient device 104 modules and applications. As mentioned above, the network module 116 may be configured to perform at least one of the following: receiving an RTS message 116, ordering the RTS message 116, reserving bandwidth for one or more sender devices 102 of the RTS message 116, generating a CTS message 126 and sending the CTS message 126 to the sender device 102 for which bandwidth has been reserved, generating a BTL message 126 and sending the BTL message 126 to other sender devices 102, tracking the number of times the BTL message 126 has been sent to a sender device 102, and receiving the data message 110 using the reserved bandwidth. Moreover, the network module 116 may perform these operations concurrently on any number of data messages 110. For example, the network module 116 may receive the data message 110 while transmitting the CTS message 126 in response to the RTS message 116 of another data message 110.

In one embodiment, when network module 116 receives RTS messages 116 via interface 120, network module 116 may queue the RTS messages in queue 124 for ordering. RTS messages 116 may be received from multiple sender devices 102, and the interface 120 receiving those RTS messages 116 may be any type of interface, such as the same or a different type of interface as the interface 118 described above. The queue 124 may be any type of data structure, such as the data structure of the network module 116.

For example, fig. 3 illustrates an example of a queue 124 that includes RTS message entries for ordering received RTS messages 116. As shown, a queue 302 (which may be an example of queue 124) includes a plurality of entries 304 of RTS messages 116. Although these entries 304 are shown as rows of a table, it should be understood that the entries 304 may equally be represented as columns or some non-tabular form of items. Each entry 304 includes a message identifier 306, a count 308 of BTL messages 126 sent to the sender device 102 in response to an RTS message 116 associated with a particular data message 110, an indicator 310 of the priority of the data message 110 associated with the RTS message 116 of the entry 304, and an identifier 312 of the sender device 102 that sent the RTS message 116 of the entry 304. Each message identifier 306 may be any type of data value, such as an integer or a string, that uniquely identifies the RTS message 116 or the data message 110 associated with the RTS message 116. Each count 308 may be an integer or some other numerical value retrieved from another data structure of the receiving device 104 that is used to track the BTL messages 126 sent in response to the RTS message 116 associated with a particular data message 110. Upon receiving the RTS message 116, the network module 116 checks the data structure for the number of BTL messages 126 associated with the data message 110 referred to by the received RTS message 116. Each indicator 310 may, for example, be one of a finite set of binary values or other value types that indicate whether it is prioritized. Alternatively, if several priority levels are available, the indicator 310 of each entry 304 may indicate a particular priority level of the data message 110. Each identifier 312 for the sender device 102 may be a network identifier, such as an IP address or other form of address, for the sender device 102.

In various embodiments, network module 116 may order RTS messages 116 in queue 124 based on any number of factors. For example, the network module 116 may order the RTS messages 116 based on message priority and/or based on the above-mentioned count of BTL messages 126. The network module 116 can also consider the bandwidth available for reservation by the receiving device and the size of the data message 110 corresponding to the RTS message 116.

Based on the ordering, the network module may reserve bandwidth for one or more sender devices 102 associated with the received RTS message 116. These may be the sender device 102 corresponding to the highest ranked RTS message 116. In some embodiments, the network module 116 may apply a maximum bandwidth reservation for the sender device 102 such that no sender device 102 may be allocated the entire available bandwidth to the receiver device 102. This maximum bandwidth reservation may prevent the sender device 102 from monopolizing the receiver device bandwidth.

To make the bandwidth reservation effective, the network module 116 sends a CTS message 126 to the sender device 102 for which bandwidth is reserved. CTS messages 126 may identify RTS messages 116 to which they respond or data messages 110 to which they provide permission. In some embodiments, where the RTS message 116 identifies multiple data messages 110, the CTS message 126 may also identify the number or identity of the multiple data messages 110.

The network module 116 may then generate and send a BTL message 126 in response to the RTS message 116 that did not result in a bandwidth reservation and CTS message 126 response. The BTL messages 126 may identify RTS messages 116 to which they respond or data messages 110 to which permission is denied. In some embodiments, where the RTS message 116 identifies multiple data messages 110, the BTL message 126 may also identify the number or identity of the multiple data messages 110. After sending the BTL message 126, the network module 116 can update the count of BTL messages for the particular data message 110 stored in the data structure of the recipient device 104 as discussed above. After responding to each entry 304 in the queue 124 with either the CTS message 126 or the BTL message 126, the network module 116 may also flush the entries 304 in the queue 124.

In various embodiments, the network module 116 may then use the reserved bandwidth to receive the data message 110. Because the recipient device 104 only receives the data message 110 to which it provided permission to send, the risk of buffer overflow at the recipient device 104 is prevented. Upon receiving the data message 110, the network module 116 provides the data message 110 to the application 128 to which they are directed and releases the bandwidth reservation associated with the data message 110. In some embodiments, completing reception of the data message 110 and releasing the bandwidth reservation triggers sending the next CTS message 126.

Example operations

Fig. 4 and 5 are flowcharts illustrating example operations of processes. Example operations of these processes are illustrated in separate blocks and are summarized with reference to these blocks. The processes are illustrated as logical flow diagrams, and each operation may represent a set of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the operations represent computer-executable instructions stored on one or more computer-readable storage media that, when executed by one or more processors, perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and so forth that perform particular functions or implement particular abstract data types. The order in which the operations are described is not intended to be construed as a limitation, and any number of the described operations can be combined in any order and/or in parallel to implement the process.

Fig. 4 is a flow diagram illustrating operations performed by a sender device to establish an active circuit with a receiver device over a packet-switched network in accordance with various embodiments. As shown at block 402, a sender device may receive a message for delivery from one or more applications of the sender device to a recipient device. The sender device and the receiver device may be connected by a packet switched network, such as a full halved bandwidth network or a high halved bandwidth network. At block 404, upon receiving the message, the sender device may determine whether the message is a control message or has a size less than a threshold size. At block 406, if the message is a control message or less than a threshold size, the sender device may transmit the message to a recipient device designated by the message. At block 408, if the message is not a control message or is greater than a threshold size, the sender device queues the message for subsequent transmission.

At block 410, the sender device selects a message for delivery to the recipient device. The sending device may select a message from a sending device queue, such as the first message in the queue. In some embodiments, the sender device may select multiple messages for transmission, such as multiple messages for linking transmission to the same recipient device or multiple messages to multiple recipient devices. At block 410a, the sender device limits the number of selected messages based on the available transmission bandwidth of the sender device so that all selected messages can be transmitted concurrently without having to wait for any other selected messages to complete transmission. At block 410b, the sending device may select a message from the queue that is associated with a previous Request To Send (RTS). The sending device may have a previously sent RTS for the message and may receive a response denying permission to send the message.

At block 412, the sender device sends an RTS for the selected message. The RTS may include the size of the message. In some embodiments, the sending comprises: multiple requests are sent via multiple interfaces of the sending device that share the same message queue and set of queue states. In one embodiment, the RTS may be sent via an interface other than a message. At block 412a, the sending device sends multiple RTS's in parallel to multiple receiving devices. At block 412b, the sender device links an RTS destined for a single receiver device and concurrently sends a linked RTS to the receiver device. At 412c, the link may include: the number of messages that the sender device needs to send to the receiver device is indicated in a single RTS.

In response to the RTS, the sending device receives a Clear To Send (CTS) message at block 414 or a response denying the RTS (referred to herein as a "busy retry-later" (BTL) message) at block 422. At block 414, the sender device receives a CTS from the receiver device. RTS and CTS establish an efficient circuit between a sender device and a receiver device over a packet-switched network. The receiver device sends the CTS message to the sender device for which bandwidth is reserved. At block 416, the sender device determines which messages are permitted by the CTS. For example, if the sender device indicates at block 412c that the sender device has ten messages to transmit, the recipient device may only respond with one or more CTS's that permit five of the messages. At block 418, the sender device sends the licensed one or more messages to the receiver device, which will use the reserved bandwidth to receive the licensed one or more messages. By utilizing the full bandwidth of the sender device and the reserved bandwidth of the receiver device, the sender device ensures that the message is sent without any delay, packet loss, or unused bandwidth.

At block 420, the sender device utilizes a timer to estimate when the next message should be delivered to the recipient device. The timer estimates the time at which the selected message or messages are to be sent and thus when message delivery will be complete and when the sender device bandwidth will be available.

At block 422, instead of receiving the CTS, the sender device receives a BTL from the receiver device that rejects the request to send message. At block 424, in response to the BTL, the sender device selects another message to send to another recipient device. In some embodiments, a sending device selects a first message in a queue whose RTS has not been sent and is directed to another receiving device. RTS messages for other messages are then sent at block 412. The sending device selects another message to transmit if the RTS is denied to ensure that the sending device is not quiesced idle but still has messages to transmit and available bandwidth to transmit those messages.

Fig. 5 is a flow diagram illustrating operations performed by a receiver device to establish an efficient circuit with a sender device over a packet-switched network based on reservation of bandwidth by the receiver device, in accordance with various embodiments. As shown at block 502, a receiving device may receive a plurality of Request To Send (RTS) messages from a plurality of transmitting devices. In some embodiments, the RTS message includes the size of the message that the sending device is requesting to send. Upon receiving the RTS messages, the receiving device may order the RTS messages at block 504 based at least on one of a priority included in one or more of the RTS messages or a number of times the sending device has received a response denying its RTS message.

At block 506, the receiver device may reserve bandwidth for at least one sender device to receive messages from the at least one sender device. The at least one sender device may have its RTS message selected from the ordered RTS messages. In some embodiments, the receiving device reserves bandwidth for receiving a plurality of messages corresponding to the plurality of RTS messages from the receiving device. Also, in other embodiments, the number of sender devices for which bandwidth is reserved may be related to the message size of the sender device that is requesting transmission. The receiving device then responds to the one or more RTS messages of the at least one transmitting device, providing one or more Clear To Send (CTS) messages to the at least one transmitting device using the reserved bandwidth, at block 508.

At block 510, the receiving device responds to the other sending devices with a response rejecting the other sending devices' RTS messages. These negative responses are referred to herein as "busy later retry" (BTL) messages. The BTL message indicates to the other sender devices that they should send RTS messages to other receiver devices in order to fully utilize the bandwidth of their sender devices. In some embodiments, when a recipient device sends a BTL message to a sender device, it increments a representation of the number of BTL messages sent to the sender device. The representation is then used for subsequent sorting operations.

At block 512, the receiver device receives one or more messages from the at least one sender device using the reserved bandwidth.

Example System architecture

Fig. 6 is a block diagram of an example computer system architecture for a sender device 102 or a receiver device 104, in accordance with various embodiments. As shown, the sender device 102/receiver device 104 may include at least a memory 602 (including cache memory) and one or more processing units (or processors) 604. Processing unit 604 may be implemented in hardware, software, firmware, or a combination thereof, as appropriate. A software or firmware implementation of processor 604 may include computer or machine executable instructions written in any suitable programming language for performing the various functions described. Processor 604 may also or alternatively include one or more Graphics Processing Units (GPUs).

Memory 602 may store program instructions that are loadable and executable on processor 604, as well as data generated during execution of these programs. Depending on the configuration and type of computing device, memory 602 may be volatile (such as Random Access Memory (RAM)) and/or non-volatile (such as Read Only Memory (ROM), flash memory, etc.). The computing device or server may also include additional removable storage 606 and/or non-removable storage 608, including, but not limited to, magnetic or optical disks and/or tape. The disk drives and their associated computer-readable media may provide non-volatile storage of computer-readable instructions, data structures, program modules, and other data for the computing device. In some implementations, the memory 602 may include a variety of different types of memory, such as Static Random Access Memory (SRAM), Dynamic Random Access Memory (DRAM), or ROM.

Computer-readable media includes at least two types of computer-readable media, namely computer storage media and communication media.

Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, erasable programmable read-only memory (EPROM), flash memory or other memory technology, compact disc read-only memory (CD-ROM), Digital Versatile Disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information for access by a computing device.

In contrast, communication media may embody computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave or other transport mechanism. As defined herein, computer storage media does not include communication media.

The sender device 102/receiver device 104 may also contain a communication connection 610, such as the network 106, that allows the sender device 102/receiver device 104 to communicate with a stored database, another computing device or server, a user terminal, and/or other devices on the network. The sender device 102/receiver device 104 may also include input devices 612, such as a keyboard, mouse, pen, voice input device, touch input device, etc., and output devices 614, such as a display, speakers, printer, etc.

The sender device 102/receiver device 104 may further include an interface 118/120 for sending and receiving data across the network 106. As mentioned above, interface 118/120 may include any number of network interfaces, each having an associated bandwidth for transmitting and receiving data.

Turning to the contents of the memory 602 in more detail, the memory 602 may include a platform 616. Platform 616 may include an operating system and/or one or more applications or services. If the memory 602 belongs to the sender device 102, the memory 602 may further include a network module 108 and an application 112, which network module 108 and application 112 may each represent any one or more modules, applications, processes, threads, or functions, and one or more queues 114, which queues 114 may represent any storage format or data structure. The network module 108, application 112, and queue 114 are described in more detail above. If the memory 602 belongs to the recipient device 104, the memory 602 may further include a network module 122 and an application 128, which network module 122 and application 128 may each represent any one or more modules, applications, processes, threads, or functions, and one or more queues 124, which queues 124 may represent any storage format or data structure. The network module 122, application 128, and queue 124 are described in more detail above.

Final phrase

Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described. Rather, the specific features and acts are disclosed as example forms of implementing the claims.

Claims (6)

1. A method for communicating in a packet switched network, comprising:

sending, by a sender device, a request to a receiver device connected to the sender device over a packet network, the request being associated with a bandwidth reservation from the receiver device for receiving messages from the sender device and the request indicating a first number of messages that the sender device needs to send to the receiver device;

receiving, by the sender device from the receiver device, a response that provides permission to send a second number of messages, less than the first number of messages, to the receiver device using the reserved bandwidth of the receiver device, the request and the response creating an efficient circuit between the sender device and the receiver device over the packet-switched network.

2. The method of claim 1, further comprising:

determining whether another message is a control message or less than a threshold size; and

in response to determining that the other message is a control message or is less than a threshold size, sending the other message to the recipient device without having to send a prior request associated with bandwidth reservation.

3. The method of claim 1, further comprising sending multiple requests to multiple recipient devices in parallel.

4. The method of claim 3, further comprising limiting a number of requests sent based on available bandwidth of the sender device.

5. The method of claim 1, further comprising concurrently sending multiple requests for multiple messages to the recipient device.

6. The method of claim 1, wherein the request indicates a number of messages that the sender device needs to send to the receiver device, and further comprising receiving a response that provides permission for some or all of the messages.