Network bandwidth regulation using traffic scheduling
24 claims: 4 independent, 20 dependent
- 1集中型のトラフィックマネージメントサーバー が 少なくとも一つのクライアントノードによって送信される着信パケットのサンプル を 連続的にモニターする ように、前記トラフィックマネージメントサーバーを使用してネットワーク経由でデータトラフィックをモニターする ことと、 前記 トラフィックマネージメントサーバー が 着信パケットの前記サンプルの頻度、変化率およびコンテンツに基づい て 負荷情報を演算する ように、ネットワーク負荷を予測する ことと、 前記 トラフィックマネージメントサーバーと前記少なくとも一つのクライアントノード とが データパケットの今後の送信用にスケジュールされた時間を決定するメッセージを交換する ように、ネットワークトラフィックをスケジューリングする ことと、 前記少なくとも一つのクライアントノード が 前記スケジュールされた時間に前記ネットワーク経由 で 前記データパケットを送信する ように、データを送信する ことと、 を含むコミュニケーションネットワークの帯域幅を調整する方法。
- 2必要ならば、さらに、前記データパケットを再送信することを含み、もし、前記トラフィックマネージメントサーバーからアクノリッジメントが受信されないならば、前記少なくとも一つのノードが前記データパケットを再送信することを特徴とする請求項1に記載の方法。
- 3前記ネットワークが、インタラクティブなデジタルケーブルテレビネットワークであることを特徴とする請求項1に記載の方法。
- 4前記ケーブルテレビネットワークが、ユーザデータグラムプロトコル(UDP)上のハイパーテキストトランスファープロトコル(HTTP)を使用して、複数のセットトップボックスと、アウトオブバンドチャネルを経由にてコミュニケーションするエンハンスドテレビジョンプラットフォームサーバーを含むことを特徴とする請求項3に記載の方法。
- 5前記セットトップボックスが、EBIFユーザエージェント上で作動しているエンハンスドテレビジョンバイナリーインターチェンジフォーマット(EBIF)を使用して実施されるインタラクティブなアプリケーションを起動することを特徴とする請求項4に記載の方法。
- 6前記トラフィックが、インタラクティブなアプリケーションコミュニケーション、ボーティングとポーリングデータ、テレビ利用状況データ、ユーザ嗜好と統計トラフィック、および、Tコマース情報の内の少なくとも一つを含むことを特徴とする請求項1に記載の方法。
- 7前記スケジューリングすることと前記送信することが、 前記トラフィックマネージメントサーバー上のネットワークトラフィック状況に応じて送信・確率の値を設定することと、 前記送信・確率の値およびクロック同期情報を、前記トラフィックマネージメントサーバーから前記少なくとも一つのクライアントノードへ送信することと、 前記送信・確率の値および同期情報を、前記少なくとも一つのクライアントノードにおいて、ランダム化したデータ送信タイムを演算するために利用することと、 前記演算されるランダム化したデータ送信タイムに、前記少なくとも一つのクライアントノードにより、データパケットを送信することと、 前記トラフィックマネージメントサーバーによって前記少なくとも一つのクライアントノードへアクノリッジメントパケットを発生して送信し、そこでは、前記アクノリッジメントが前回の送信の成功を示して次回の送信用の新しい送信・確率の値を提供していることと、 もしアクノリッジメントパケットが受信されなかったならば、新しいデータ送信タイムに、前記少なくとも一つのクライアントノードよって前記データパケットを再送信することと、 を含むことを特徴とする請求項1に記載の方法。
- 8前記送信・確率の値が、タイムウィンドウに反比例しており、前記次回のパケットが送信されるべきで、前記ランダム化したデータ送信タイムが前記ウィンドウ内でランダムタイムであり、前記アクノリッジメントパケットとデータパケットの各々が、前記ウィンドウ内で、ディスクリートなタイムスロット境界上で送信されることを特徴とする請求項7に記載の方法。
- 9前記送信・確率の値が、伝送エラーおよびアクノリッジメントタイムアウトなしで、時間の経過とともに、前記少なくとも一つのクライアントノードにて、漸進的に増加されることを特徴とする請求項7に記載の方法。
- 10前記送信確率が、送信エラーとアクノリッジメントタイムアウトの内の少なくとも一つに応じて減少されることを特徴とする請求項7に記載の方法。
- 11前記トラフィックマネージメントサーバーから送信・確率の値およびクロック同期情報を前記送信することが、前記少なくとも一つのクライアントノードへの周期的なブロードキャストを経由して行われることを特徴とする請求項7に記載の方法。
- 12前記トラフィックマネージメントサーバーから送信・確率の値およびクロック同期情報を前記送信することが、少なくとも一つの個別にアドレスされたクライアントノードへのナローキャストを経由して行われることを特徴とする請求項7に記載の方法。
- 13前記トラフィックマネージメントサーバーから送信・確率の値およびクロック同期情報を前記送信することが、前記少なくとも一つのクライアントノードが前記トラフィックマネージメントサーバーへ前記データパケットを送信する権利をリクエストするプローブデータパケットを送信した後に、生じることを特徴とする請求項7に記載の方法。
- 14前記ネットワークが、インバンドケーブルテレビ、DSL、または、モバイルブロードバンドネットワークであることを特徴とする請求項1に記載の方法。
- 15前記ネットワークが、ユーザデータグラムプロトコル(UDP)、または、送信制御プロトコル(TCP)を利用することを特徴とする請求項1に記載の方法。
- 16前記トラフィックマネージメントサーバーが、トラフィックマネージメント情報を具備する少なくとも一つのUDPパケットを少なくとも一つのTCPパケットへ変換するUDP→TCPリレーサーバーとしての役割を果たすことを特徴とする請求項1に記載の方法。
- 17前記少なくとも一つのクライアントノード上で作動しているトラフィックマネージメントクライアントが、トラフィックをスケジューリングすることとデータを送信すること、および、クライアントアプリケーションをサポートしてデータを再送信することとをマネージすることを特徴とする請求項2に記載の方法。
- 18前記トラフィックマネージメントクライアントが、前記クライアントアプリケーション用の標準ストリームソケットアプリケーションプログラミングインターフェースを模倣して、単一データグラムソケットまたはポートを使用しながら、複数の同時仮想ストリームソケットおよび接続を提供することを特徴とする請求項17に記載の方法。
- 19前記クライアントアプリケーションが前記データを送信する前の前記スケジュールされたデータ送信時間を待つように、データの前記送信および再送信が、同期方式で実施されることを特徴とする請求項17に記載の方法。
- 20前記ネットワークがデータ送信の準備ができた時に、コールバックが前記トラフィックマネージメントクライアントによって前記クライアントアプリケーションへ発行されるように、データの前記送信および再送信が、非同期方式で実施されることを特徴とする請求項17に記載の方法。
- 21前記スケジューリングし、送信し、再送信するステップが、前記少なくとも一つのクライアントノード上で作動している少なくとも一つのアプリケーションにさらされており、ユーザ側の動作を調整するために使用されることを特徴とする請求項2に記載の方法。
- 22データの前記送信および再送信が、さらに、静的テーブルを使用して前記データを圧縮することを含み、そこでは、ストリング値を有する複数の標準HTTPメッセージエレメントに、それぞれ、テーブルインデックスが割り当てられ、前記インデックスが前記ストリング値の代わりに送信され、前記ストリング値が前記静的テーブルを利用することで受信時に再構築されることを特徴とする請求項2に記載の方法。
- 23さらに、外部イベントに積極的に応答する帯域幅調整サーバーを含み、前記外部イベントが、時刻帯域幅負荷、時季帯域幅負荷および緊急ニュース速報の中から選択されることを特徴とする請求項1に記載の方法。
- 24ネットワークと、 少なくとも一つのクライアントノードと、 集中型のトラフィックマネージメントサーバーと、 を含み、 前記トラフィックマネージメントサーバーは、 前記トラフィックマネージメントサーバー が 前記少なくとも一つのクライアントノードによって送信される着信パケットのサンプル を 連続的にモニター するように、前記ネットワーク経由でデータトラフィックをモニターし、 前記 トラフィックマネージメントサーバー が 着信パケットの前記サンプルの頻度、変化率およびコンテンツに基づい て 負荷情報を演算 するように、ネットワーク負荷を予測し、 前記トラフィックマネージメントサーバーと前記少なくとも一つのクライアントノード とが データパケットの今後の送信用にスケジュールされた時間を決定するメッセージを交換するように 、ネットワークトラフィックをスケジューリングする、 ように構成されている、 コミュニケーションネットワークの帯域幅を調整するシステム。
Independent claims24
220 paragraphs, as filed
The present invention generally relates to systems and methods of adjusting network bandwidth. More specifically, various embodiments relate to traffic reporting and bandwidth reservation mechanisms.
Concerns about network congestion are due to the continued spread of communication networks from the Internet to cable TV, IPTV, mobile broadband, Wi-Fi, home networks and the ever-increasing demand for data transmitted over these networks. , Is becoming more pervasive. As fast as it can provide larger pipes, user demands threaten to meet them. The best effort mechanisms for data delivery, such as those that underpin the Internet, often turn out to be inadequate.
Network congestion concerns will be especially acute for narrow, asymmetrical channels such as out-of-band (OOB) channels in cable TV networks. OOB cable channels are increasingly subject to the demand for handling traffic generated by enhanced TV applications, such as those implemented using the Enhanced TV Binary Interchange Format (EBIF) or Open Cable Application Platform (OCAP) standards. is nervous. Such traffic will include voting and polling data, user preference and statistical traffic, T-commerce information and other data. Data distribution over DSL and mobile broadband networks faces similar challenges.
Various approaches have been described to address the challenges of network congestion on bandwidth-restricted networks. Some approaches include: That is, packet dropping (via "tail drop" or active queuing management), TCP congestion avoidance, explicit congestion notification, window shaping, traffic shaping (ie, packet delay), quality of service (QoS) schemes, and , Related bandwidth reservation technology.
What is needed is a method that allows the node to continue processing without requiring long messages, excessive handshakes or other QoS type overhead while waiting to send and receive data. A system and method of adjusting network bandwidth to reduce congestion.
In various embodiments, systems and methods utilize traffic reporting and bandwidth reservation mechanisms to regulate network bandwidth, including monitoring network traffic, predicting network load, and scheduling traffic. Will be provided. Traffic reporting will include broadcasting control messages to network nodes that indicate the appropriate number of times to send and receive messages. Network nodes will use traffic reports (eg, control messages) to proactively coordinate their use in the network. Reservations will be made synchronously or asynchronously. The reservation mechanism will emulate the traditional stream socket API.
In another embodiment, in addition to the traffic report broadcast, the client node will make a bandwidth reservation before sending or receiving a message or other data.
In some embodiments, the system and method provide bandwidth adjustment and lightweight transmission control protocol (TCP) functionality over User Datagram Protocol (UDP) in a digital cable TV out-of-band (OOB) network. There would be a hypertext transfer where the Enhanced Television (ETV) platform server is interchanged using UDP with an Enhanced TV Binary Interchange Format (EBIF) user agent running multiple set-top boxes (STBs). Communicating via a protocol (HTTP) payload.
Other embodiments include networks that utilize TCP and other protocols, networks such as in-band cable TV, DSL and cellular / mobile networks, and networks based on other architectures and components.
In another embodiment, bandwidth throttling will be performed by the EBIF user agent in a way that would be obvious to the EBIF application. In another embodiment, the traffic schedule will be exposed to a network application, from which the disclosed traffic scheduling mechanism can be used and user-side behavior can be adjusted appropriately.
In another embodiment, the bandwidth throttling server will be responding to external events (eg, time-of-day or seasonal bandwidth forecasts, perhaps breaking news indicating a traffic storm) in order to be properly managed.
It should be understood that both the general description above and the detailed description below are exemplary and explanatory only and do not limit the claimed invention. The accompanying drawings form part of this specification, exemplify some embodiments of the invention, and serve to explain the principles of the invention, along with detailed descriptions.
The present invention can be more fully understood by reading the following detailed description, along with the accompanying drawings, in which similar references are used to specify similar elements. In addition, it is as follows. That is,
<figref num="1">Is an exemplary architectural diagram illustrating an embodiment of a system that provides bandwidth throttling in an out-of-band network of cable systems.</figref>
<figref num="2">Is an exemplary architectural diagram illustrating an embodiment of a traffic management server according to an embodiment of the present invention.</figref>
<figref num="3">Is an exemplary architectural diagram illustrating a programmer diagram of an embodiment of a traffic management client according to an embodiment of the present invention.</figref>
<figref num="4(a)">Is a flow chart depicting a traditional HTTP TCP / stream socket implementation.</figref>
<figref num="4(b)">Is a flowchart illustrating an HTTP synchronous (blocking) virtual socket implementation according to an embodiment of the present invention.</figref>
<figref num="4(c)">Is a flowchart illustrating an asynchronous (non-blocking) virtual socket implementation of HTTP according to an embodiment of the present invention.</figref>
<figref num="5(a)">Is a graphic representation of an exemplary information packet.</figref>
<figref num="5(b)">Is a graphic representation of an exemplary data packet.</figref>
<figref num="5(c)">Is a graphic representation of an exemplary ACK packet.</figref>
<figref num="5(d)">Is a graphic representation of an exemplary probe packet.</figref>
<figref num="6(a)">Is a graphic display of the virtual socket structure.</figref>
<figref num="6(b)">Is a graphic representation of the virtual socket table structure.</figref>
<figref num="6(c)">Is a graphic display of the reserved queue structure.</figref>
<figref num="7(a)">Is a graph depicting a simulation of network load without bandwidth throttling.</figref>
<figref num="7(b)">Is a graph depicting a simulation of a network load with bandwidth throttling.</figref>
<figref num="7(c)">Is a graph depicting the difference between simulated network loads with and without bandwidth throttling.</figref>
As illustrated in Figure 1, the present disclosure relates to network bandwidth throttling using traffic scheduling in the context of traffic management (TM) systems 100 and methods. More specifically, an embodiment is disclosed in the context of a digital cable TV out-of-band (OOB) network, where the Enhanced Television (ETV) Platform Server 200 is an Enhanced TV Binary Interchange Format (EBIF) user. Communicate via Hypertext Transfer Protocol (HTTP) payloads that are exchanged with each other using User Datagram Protocol (UDP) with multiple set-top boxes (STBs) 400 that launch agents 410. In addition to providing bandwidth throttling, the disclosed TM System 100 and methods are lightweight transmission control protocols (TCP) that use UDP to support guaranteed delivery, packet sequencing, flow control and data compression. Will provide functionality.
The systems and methods described herein are also for use with traffic utilizing TCP and other protocols, for other networks such as in-band cable TV, DSL and cellular / mobile networks, and for others. Would be appropriate for architecture- and component-based networks.
In this embodiment, the TM system 100 and method take into account the following characteristics of the digital cable OOB network: That is,
Asymmetry: Downstream network bandwidth (headend STB) is wider than upstream.
Low bandwidth: Bandwidth in either direction is measured in Kbps instead of Mbps.
Long latency: Tunneling Internet Protocol (IP) on a hybrid fiber-coaxial (HFC) network causes latency.
UDP over TCP: Saves bandwidth and time, and not all cable OOB networks offer TCP.
HTTP dominates: Most traffic is modeled on HTTP requests / responses, but there will be exceptions.
Request / response dichotomy: Most traffic consists of data that travels in one or the other direction, and tends to carry much less data in the request direction.
Vulnerability: Upstream congestion will crash OOB networks and STBs on the network.
Mixed Foreground / Background: Some requests require a timely response, while others do not. Assumptions and definitions
To facilitate the description of current embodiments, the following assumptions will be made for the basic network. That is,
Cable OOB networks use IPv4 exclusively, not IPv6.
The IP packet header occupies 20 bytes.
The UDP packet header occupies 8 bytes.
A media access control (MAC) layer cell has a payload of at least 34 bytes (varies in size).
The maximum UDP message size that can fit in a MAC cell with 28 bytes of IP and UDP headers is 34-28 = 6 bytes. This drives the size of the TM packet header.
The total upstream bandwidth per hybrid fiber coaxial network node (HFC node, ie demodulator) is 256 Kbps, shared between 500 and 2000 STB.
The slotted Aloha network has a theoretical maximum efficiency of 36.8% due to collisions.
The total downstream bandwidth per modulator is shared up to 32,000 STB and is 2 Mbps.
The performance of the current example will be based on the following numerical constants that will be used in the implementation: It has been pointed out that the representative values may change based on the characteristics of the experiment and the following deployment environment. That is,
The maximum transmission unit (ie UDP packet size) for MTU: TM upstream traffic would be 244 bytes or 1952 bits. This allows one MTU to fit exactly within six MAC cells (272 bytes), including 28 bytes of IP and UDP headers. 99% of all upstream messages should fit in 1 MTU. Downstream will have a larger MTU and can be up to 987 bytes.
SLOT: The time required to send one MTU at 256Kbps or 0.008 seconds (8 milliseconds).
SLOTS_PER_SECOND: constant 125 (ie 1000ms / sec / 8ms / SLOT).
A 6-byte (or larger) unsigned integer that uniquely identifies a SLOT (ie, an 8ms time slice) since 01/01/2000 with SlotID: 00:00:00. That is, a SlotID of 0 points to an 8ms time slice that starts at 00: 00: 00.000 on 01/01/2000 and ends at 00: 00: 00.008 on 01/01/2000, and SlotID2 is 00: Refers to the next time slice, starting at 01/01/2000 at 00: 00.08 and ending at 01/01/2000 at 00: 00: 00.016. For example, the SlotID of the 34th SLOT for the date and time of May 8, 2010 3:21:04 AM is 40825580834. The slot ID of the first SLOT representing the 100th anniversary second of this date is 242007908000.
VPORT: Actual number of ports used for all TM traffic (1962). This number is registered with BIAP.
VSEND_WASTE: Maximum number of milliseconds between packets that a data transmission function (eg vsend ()) should continue to block. Initially, it is set to 100 milliseconds.
VSEND_TRIES: Maximum number of packet retransmissions that vsend () should try before returning. Initially set to 5.
VRECV_WASTE: The maximum number of milliseconds that a data receiving function (for example, VRECV ()) should wait for a data packet and continue to block. Initially set to 100 milliseconds. Traffic management architecture
FIG. 1 is an exemplary architectural diagram illustrating an embodiment of System 100 that provides bandwidth throttling in an OOB network of cable systems. The depicted TM Client 420 and TM Server 210 components will provide TCP-like functionality over UDP with built-in bandwidth throttling.
This embodiment was installed on a cable operator headend that communicates with multiple hubs (not shown) and multiple STB400s installed on the customer premises connected via HFC nodes 300 in a tree-branch topology. It will consist of one or more ETV Platform Servers (EPS) 200. EPS200 relays incoming TM / UDP traffic consisting of HTTP payload to Apache HTTP Server 220 via HTTP / TCP, and then reverses HTTP / TCP response via M / UDP via intermediate HFC node 300 and hub. Will have a TM server 210, which would be a high performance UDP proxy server, relaying to the source STB400.
The STB (ie, client node) 400 will include an EBIF user agent 410 that utilizes the TM client 420 to support the data networking needs of EBIF applications (not shown) running on the STB 400. TM Client Component 420 mimics a standard stream socket application programming interface (API) for TCP networking that provides multiple simultaneous "virtual" stream sockets and connections while using only a single real datagram socket / port. , Would be a static library.
The TM / UDP protocol shown will use simple packet fragmentation, sequencing and recognition schemes to ensure message delivery. Bandwidth throttling is controlled by TM Server 210, which will monitor upstream traffic to predict network load, and tells TM Client 420 how to schedule upstream messages (eg, bandwidth). Will broadcast a control message to the STB400 telling (via reservation). Downstream bandwidth throttling will be fully achieved within TM Server 210.
Given the architecture depicted in Figure 1, there will be three modes of operation supported, and only one will be used for any special cable operator. Which modes are supported are (a) availability of a continuous trickle of downstream bandwidth for UDP broadcasting of load information to STB400, (b) one socket / port resident on the client system. Will depend on assignments (a) and (b). These modes would be: That is,
Mode 1: When both (a) and (b) are available, TM Server 210 sends information packets (see below) to all STB400s periodically, eg, during heavy load conditions. Will broadcast every second or more often. This should require about 30bps (0.03Kbps).
Mode 2: These packets are sent more often when (a) is available but (b) is not and the TM client 420 has to wait for information packets before sending any message. It must be. This should require about 270bps (0.27Kbps).
Mode 3: When (a) is not available, the probe packet (described below) must be used to "see the journey" before sending all messages. This causes a concise bandwidth spike beyond the configured limits and is therefore less preferred than the other modes. Traffic management server
FIG. 2 is an exemplary architectural diagram illustrating an embodiment of the Traffic Management (TM) Server 210.
The TM server 210 would be a high-performance UDP TCP relay server that implements TM with guaranteed delivery protocol and OOB bandwidth throttling. Incoming connections and data will be received via UDP listener process 214, and connections / packets will be placed as tasks on agenda 218. Agenda 218 will be read by several processes, as depicted by the dashed line in Figure 2.
Each time a data or probe packet arrives with a new combination of IP address, port and ConnID (see packet format section below) header fields, the connection will be implicitly "opened". Multiple child processes 216, each running multiple worker threads, will process these packets as they arrive, reconfigure them into the original message in the proper order, and clients as needed. Returns an ACK packet to. The completed message will then be sent to the Apache HTTP server 220 over a standard HTTP / TCP / IP connection. The HTTP response from Apache will then be returned to the corresponding client via an "open" virtual connection (ie, via a downstream data packet).
Bandwidth throttling process 212 will monitor incoming packages in real time. This information and its rate of change will be used to estimate load trends. From this estimate, the corresponding transmission probabilities will be calculated. This transmission probability and clock synchronization information will be periodically broadcast to all TM clients 420 via UDP. Traffic reporting
This section describes an exemplary method for communicating load information to TM Client 420.
TM Server 210 and TM Client 420 will manage upstream OOB bandwidth by increasing the time used to send messages. All messages will be split into multiple fixed size data packets, and each packet will be bound with a random delay. For example, if the current wide area transmission probability (ie variable send_probability) is 32767, the delay (in SLOT) would be calculated as: That is,
tm_random ()% (131072.0 / 32768 + 0.5) = tm_random ()% 4
This results in a value between 0 and 3. For example, if tm_random () returns 446, then 446% 4 = 2. A call to the channel / slot reservation function on the TM client 420 will return a reservation delay of 16 ms to the caller (ie 8 * 2, where each SLOT is 8 ms). .. This information will also be used to update reservation_slot, which is variable with a delay of 2 to the current SlotID value. This is interpreted to mean that the first virtual connection in the reserved queue maintained by TM Client 420 has a packet to send 16 milliseconds (ie, 2 SLOT) from now. Subsequent calls to the reserved function will then return 0 to the caller who understands that the reserved time has arrived and then sends the message. The send_probability value will be set as follows: That is,
(1) It is initialized to the default value of 16,387.
(2) In modes 1 and 2, the value is received directly from the information packet broadcast by the TM server 210. This value replaces any older send_probability value. In mode 3, the probe packet is sent as soon as possible to generate the corresponding ACK packet.
(3) All ACK packets contain an update of the send_probability value. This value replaces any older send_probability value.
(4) Send_probability is halved (minimum 1) each time the transmitted packet acknowledgement times out (ie, the packet is not acknowledged). Every second that elapses without sending_probability being halved in this way, send_probability is increased by 100 up to a maximum of 16,387.
As mentioned above, mode 1 generates a broadcast stream of information packets that require a downstream bandwidth of approximately 0.03 Kbps. Mode 2 requires 0.27 Kbps. Depending on the mode, the client should start listening for information packets as soon as possible after the true socket is available. Random number generation
This section presents exemplary implementations of random number generators (ie, tm_random () and tm_randomize ()) suitable for calculating message delays and other needs in various embodiments of the invention. That is, static unit 32 tm_seed = 19610508; Unit 32 tm_random () { const unit 32 a = 16807; const unit 32 m = 2147483647; const unit 32 q = 127773, / * m / a * / const unit 32 r = 2836, / * m% a * / int32 lo, hi, test; hi = tm_seed / q; lo = tm_seed% q; Test = a * lo-r * hi; If (if), (test> 0) tm_seed = test; Otherwise (else), tm_seed = test + m; Return tm_seed; } void tm_randomize (unit 32 s) { tm_seed = s, }
tm_randomize (<ip_address>) should be called exactly once at boot time, where <ip_address> is the unit 32 (4 bytes) value of the STB's IPv4 address. Client clock synchronization
This section describes exemplary methods of client clock synchronization suitable for various embodiments of the present invention.
Information packet broadcasts from TM server 210 will contain timing synchronization information along with send_probability updates. The timing information will go into two fields of the information packet. That is,
SynchSecond (1 byte): A value in the range 0.119 that identifies at what second the packet was sent by the server clock. This value is the offset from the latest even start.
SynchPhase (1 byte): The number of SLOTs (0..124) elapsed in sync seconds before sending this packet.
For example, if the time an information packet is built on TM server 210, including a fraction of a second, at 13: 23: 43.728 GMT, the value assigned to the SynchSecond field would be 103. Since the minute value 23 is an odd number, the most recent even number is 22. The offset from 13:22:00 to 13:23:43 is 01:43 or 103 seconds.
Once this second is identified, the remaining 0.728 seconds (728 milliseconds) must be considered. Assuming one SLOT occupies 0.008 seconds (8 milliseconds), the number of slots is calculated as 728/8 = 91. This value (eg, 91) is assigned to the SynchPhase field in the information packet.
Each time the TM client 420 receives an information packet, it will perform the following steps to update the time_offset_msec variable. That is,
(1) Calculate the current date / time (GMT) as the seconds since some epochs in the floating point variable current_time.
(2) Calculate the time defined by the two fields found in the information packet (GMT) as the seconds since the same epoch in the floating point variable current_time.
(3) Calculate the floating point variable synch_offset_msec = (synch_time & # 8211; current_time) * 1000, the latest offset in milliseconds.
(4) Set time_offset_msec = time_offset_msec * 0.9 + synch_offset_msec * 0.1. This causes a slow moving average of the time offset as the conditions change over time. Initialize time_offset_msec to zero (0) prior to receiving any information packet.
In mode 1, it may not be necessary to update time_offset_msec for each information packet. One update every minute will suffice. In mode 2, this time offset would preferably be calculated for each information packet.
Each time the "current time" is referenced, it is the STB (GMT) current time, plus the appropriate time unit (ie, if the "current time" is reported in seconds, time_offset_msec * 1000). It would be assumed to be a time_offset_msec value, scaled to. Traffic management client
FIG. 3 is an exemplary architectural diagram illustrating a programmer diagram of an embodiment of the traffic management client 420 according to an embodiment of the present invention. It is for multiple EBIF apps 430 by leveraging the socket mediation capabilities of STB middleware 440 along with the hardware provided by the client device (eg STB) 400 and other capabilities of the operating system (O / S) 450. It shows how TM Client 420 will be used by EBIF User Agent 410 to provide traffic management services. As further described, TM Client 420 utilizes a standard stream socket API, provides both synchronous and asynchronous modes for bandwidth throttling using traffic scheduling, allows both client and server connections, and multiple. Supports "virtual" sockets / ports, provides guaranteed delivery, provides data compression, and will not impose any a priori bandwidth limits. Network API
Figure 4 (a) is an exemplary flow chart depicting a traditional TCP / stream socket implementation of HTTP that will be used by networking clients. At the start (step 500), socket () will be called to get a new socket id (step 502). A connection to the server, defined by IP address and number of ports, will then be obtained by calling connect () (step 504). The request string will then be sent to the server by the send () function (step 506) and will probably require send () to make multiple calls to process all requests (step 508). After all the data has been sent (ie all sent? = Yes (step 508)), a call will be made to recv () to wait for a response (step 510). Similar to send () (steps 506, 508), multiple calls to recv () are applied repeatedly until all HTTP responses are requested (ie, all received? = Yes). ) Would (step 512). Finally, close () will be called to close the connection (step 516), after which the process will stop (step 518). Also, it may happen that not all HTTP responses are received, but the connection is closed (step 514). In this example, close () would be called to stop the process (step 518) (step 516). Implementing this type of synchronous HTTP client will be known to those of skill in the art.
4 (b) and 4 (c) describe an embodiment of an HTTP virtual socket implementation according to an embodiment of the present invention. The flowchart in Figure 4 (b) depicts a synchronous (blocking) version. The flowchart in Figure 4 (c) depicts an asynchronous (non-blocking) version.
As shown in these figures, the standard stream socket API call would be a virtual equivalent (eg send () 506 becomes vsend () 612) and stream sockets to the programmer in a well-known way. To be available. There will be a few additional functions, as shown by the shaded block. According to various embodiments of the present invention, all upstream traffic will preferably be scheduled based on the current load conditions of the network. When the network load is low, the data will be sent quickly, if not immediately. When the network load is higher, there will be a delay. The TM client 420 can estimate the expected delay from the return value of vreserve () 606, decide how to proceed or not, and use the intervening cycle for other tasks. it can.
The API call shown will be provided via a static library and will be prototyped in a C header file (.h). Such header files will #define macros that map traditional stream socket APIs to their traffic management analogs. Such macros would allow existing socket code to work with traffic management systems and methods, and would require only minor changes for outbound invocation and asynchronous processing scheduling.
The following paragraphs provide the virtual call details depicted in Figures 4 (b) and 4 (c) in the context of the disclosed steps. For all API calls described, the parameter and return types will generally refer to the same types used in traditional socket APIs, and are therefore not described here. Names beginning with the letter "v" are specific to the systems and methods described herein. Standard (ie, non-TM) socket APIs are assumed to be available as well, such as htonl (), ntohl (), getaddrinfo (), etc. Other traditional socket APIs, like poll (), select () and shutdown (), will not have analog when using traffic management.
FIG. 4 (b) is an exemplary flow chart illustrating an HTTP synchronous (blocking) virtual socket implementation according to an embodiment of the present invention.
After the process starts (step 600), the first call will be vsocket () and will assign a virtual socket descriptor (step 602). The descriptor returned by this function will be used for subsequent calls to vlisten (), vbind (), vsend () and other functions. Implementations in TM Client 420 will include allocating a new empty virtual socket structure in the virtual socket table and returning the table index of that entry as a virtual socket descriptor. In mode 2, this call will also trigger the opening and initialization of tm_socket, so it can start listening for information packets.
In the next step, the request node will call vconnect () (step 604) to connect the virtual socket to TM server 210. The relevant parameters passed to vconnect () 604 will include the virtual socket descriptor, the IP address, and the port number of the server to which it connects. If the calling program wants to identify what local port is used for the connection, a call to vbind () will be made (not depicted in Figure 4 (b)). vbind () will associate the identified virtual socket descriptor with the local IP address and the explicit number of local ports. The number of virtual socket ports will be stored in the virtual socket structure table entry indexed by the virtual socket descriptor. If vbind () was not previously called on the socket descriptor, the indicated socket descriptor would be automatically bound to the local node's IP address and random local port. This should be tolerated if the calling node is not a server, as the node probably doesn't care which local port is used. Once the virtual socket is connected, vsend () and vrecv () can be called as needed to send and receive data. The server's host IP address and port will be stored in the virtual socket table for the virtual socket structure indexed by sockfd.
A call to vreserve () (step 606) will then be made to make a reservation to send the data upstream. vreserve () 606 will accept the virtual socket descriptor (vsockfd) and return the number of milliseconds to wait before sending the message (using vsend ()). When vreserve () 606 returns zero (ie, ready to send? = Yes (step 608)), the message can be sent with the minimum probability of being blocked. The caller will perform other tasks while waiting for the reserved slot. vreserve () 606 will be called periodically to check the reservation status.
In the next step, vsend () will be used to send a message to a pre-attached server via the virtual socket returned by the vsocket () call (step 612). vsend () 612 will accept parameters as inputs indicating the connected virtual socket descriptor (vsock), a pointer to a buffer containing the data to be sent (buf) and the number of bytes to send (len). .. It will return the number of bytes actually sent. Similar to the traditional send () call depicted in Figure 4 (a) (step 506), vsend () is a synchronous (ie blocking) call before all data has been sent (ie all). Will return to? = No (step 614)). This will cause vsend () to be called repeatedly in conjunction with additional calls to vreserve () (steps 612 and 614). This is probably the case for large messages or when the network is heavily loaded.
If vsend () 612 is called and no reservation is found for the identified virtual socket, vsend () 612 internally calls vreserve () 606 and blocks until the reservation is reached. It will (ie sleep) and then start sending. If vsend () 612 is called without reservation, or before vreserve () 606 returns zero, vsend () 606 will block until it can send data. In such cases, the intervening time, perhaps a few seconds, will be wasted.
Upstream message scheduling is the first call to vreserve () 606 for a given message, or to vsend () 612 when no reservations have been made for the virtual socket in question. It will happen on the call. The vsend () 612API will provide data for the virtual socket (a) until a reservation exists in the reservation table for that virtual socket, and (b) until the SlotID in reservation_slot matches the current SlotID. Will not actually be sent. The message scheduling process will work as follows:
Assuming the call is made to vreserve (vsocket_descriptor): That is,
(1) Calculate the SlotID of the current time, where current_slot_id = # _of_whole_seconds_since_01 / 01 / 00_00: 00: 00 * 125 + fraction_of_current_second / 0.008.
(2) If vsocket_descriptor is found at position X in the reserved queue, set queue_pos = X to skip and proceed to step 5. Otherwise, set queue_pos = size_of_reservation_queue + 1.
(3) If queue_pos == 1 (that is, the queue is empty), set reservation_slot = current_slot_id + (tm_random ()% (131072.0 / send_probability + 0.5).
(4) Add vsocket_descriptor to the reservation queue.
(5) Returns (8 * (reservation_slot & # 8211; current_slot_id) * queue_pos) as a result of vreserve ().
Looking back at Figure 4 (b), after all the data was sent using vsend () (ie, all sent? = Yes (step 614)), via the pre-attached virtual socket. A call will be made to vrecv () to receive the message from the server (step 616). The vrecv () call (step 616) provides an input parameter that indicates the connected virtual socket descriptor (vsock), a pointer to the received data buffer (buf), and the size (len) of the received data buffer in bytes. Will accept. If the virtual connection to the server closes for any reason, it will return the number of bytes actually received or zero (0). Since the number of bytes actually received will be smaller than the size of the buffer, vrecv () 616 repeats until all messages have been received (ie all received? = Yes (step 618)). Will be called. If not all data has been received (ie all received? = No (step 618)) and the connection with the server has not been closed (ie the connection has been closed? = No (step 620)). If so, vrecv () will be called again (step 616).
In the case of vrecv () 616, the implementation of vrecv () 616 is vsend () 612, except that the TM client 420 must generate the appropriate ACK packet and send it back to the TM server 210. Would be similar to. Also, vrecv () 616 can operate asynchronously, so it will call after VRECV_WASTE milliseconds have elapsed without receiving a data packet from TM server 210, or when the provided receive buffer is fully filled. Should be returned to.
Returning to Figure 4 (b), if all data has been received (ie, all received? = Yes (step 618)), or the server connection has been closed (ie, the connection has been closed?). If = Yes (step 620)) is determined, the client node will call vclose () to close the virtual socket (step 622) and the process will stop (step 624). Since there will be a small number of virtual sockets available, it is important to close them when not needed. The implementation of vclose () 622 would require freeing the virtual socket structure in the virtual socket table indexed by vsockfd.
The synchronous (blocking) HTTP transaction depicted in Figure 4 (b) may be sufficient for many applications that do not need additional processing while waiting for a response to be received. However, for applications that have to perform other tasks while waiting for data, an asynchronous (non-blocking) callback mechanism will be implemented as depicted in Figure 4 (c). This async mechanism would be different from the known select API, but would be much easier to implement using.
Now, referring to FIG. 4 (c), the initial steps are the same as those in FIG. 4 (b). When starting the process (step 600), vsocket () is called to allocate the virtual socket descriptor (step 602). Then vconnect () is called to connect the virtual socket to TM server 210 (step 604).
Then vasynch () is called to associate the virtual socket with the asynchronous callback function (step 605). This function is for the virtual socket descriptor (vsockfd) obtained via vsocket () and the callback function that refers to vsockfd, message code (msg) and any activity-specific information (data). Will accept references and. All future activity on the virtual socket (eg errors, reservations, received data, etc.) will invoke a callback function to identify the appropriate message code to identify the activity. The message code would be: That is,
VAERROR: Check verrno for the actual error code.
VARESOPEN: Reservations opened via vreserve () are open here. Send data via vsend ().
VAGOTDATA: Data was received for this virtual socket. Call vrecv () to get it.
VAGOTCONN: A new connection has arrived on this virtual socket. Call accept () to get it.
The implementation of vasynch () 605 would require storing the virtual socket callback function in a virtual socket structure table entry indexed by the virtual socket descriptor. If the connection is established and the message sends upstream, the ConnID in the packet header will be used to identify the receiving virtual socket. For alert messages, the header space for ConnID and SeqNum will be taken up by TM Server 210 and used to store the number of ports. This port will be used to identify the bound socket to receive alerts (see the Packet Format section below for more information on ConnID, SeqNum and packet headers). thing).
Continuing with Figure 4 (c), after vasynch () is called (step 605), a call to vreserve () will be made to make a traffic reservation on the indicated socket (step 606). And the process stops (step 607).
As shown in Figure 4 (c), the sending and receiving processes are asynchronous and rely on a callback function (ie, my_callback ()) to start each process. The dotted arrows in the figure depict the period during which other tasks will be performed between callback activations. Specifically, the process of sending data starts with the callback function indicated by my_callback () (step 610) (step 609), followed by a call to vsend () (step 612), and then the process stops. (Step 613). The process of receiving data is similar. It starts with a callback function (ie, my_callback () 610) (step 615), followed by the same data receiving step described in Figure 4 (b). vrecv () will be called (step 616) until all data is received (step 618) or the server connection is closed (step 620), and then a call to vclose () (step 622). ) Will be done and processing will stop (step 624).
Two additional functions that may be useful, not depicted in Figure 4 (b) or Figure 4 (c), include vlisten () and accept (). The vlisten () call will be used by a node that needs to act as a server to listen for incoming connections on the indicated (ie passed) bound virtual socket (vsockfd). Such functionality would be appropriate for nodes waiting for a connection from an application server (eg for alert messages). Before calling vlisten (), calls to vsocket () and vbind () should be made to allocate virtual sockets and define the ports to listen on (each). Synchronization listening training many applications (e.g., OOB cable network STB in h) Nothing since would not make sense in, calls to asynch () is needed to make the virtual socket asynchronous right. The vlisten () call will return immediately and the asynchronous callback function will be invoked with a VGOTCONN message when the connection arrives. A vaccept () call will be defined and used to accept such new connections. Any asynchronous virtual socket bound to a port via vbind () will receive a VGOTCONN message when the connection arrives. The vaccept () call will accept the connection and return a new synchronous virtual socket descriptor that can be used to send and receive data. The original listening socket descriptor (vsockfd) will remain unchanged and will still be listening. The virtual socket descriptor returned by vaccept () will be closed using vclose () when it is no longer needed.
In another embodiment of the HTTP virtual socket implementation according to one embodiment of the invention, the reserved functions provided by vreserve () 606 call vsend () 612 and vrecv () 616, and vreserve () 606 not provided. Will be included in. In this embodiment, in addition to vsend () 612 and vrecv () 616, which return the number of bytes sent or received (respectively), each call makes the bandwidth reservation transparent so that the data is sent or received immediately. If not, it will return a negative number representing the number of milliseconds until a transmit or receive slot is available. This is the same way as shown in the vreserve () 606 ~ vsend () 612 loop depicted in Figure 4 (b), where additional processing occurs on the client node while waiting to receive the data. Allowing this would be advantageous for use in the blocking implementation of vrecv () 616. It will also simplify the API by removing one non-standard call (vreserve () 606). Packet format
To manage multiple types of traffic on a single pipe, one embodiment of the invention is four separate message packets as specified below with respect to FIGS. 5 (a) to 5 (d). Will define the type. These will include the TM / UDP protocol shown in Figure 1. Information packet
FIG. 5 (a) is a graphic depiction of an exemplary information packet 700. The TM server 210 will broadcast these small UDP messages to all STB400s simultaneously to communicate information about system load status and timing synchronization. The information packet 700 will include: That is,
PacketType702 (1 byte): A constant that identifies a valid TM packet and identifies which of the four types it is. All TMPacketType values 702 will contain a high 6-bit 0xA8 that can be used as a filter mask. The lower 2 bits vary depending on the packet type. For information packet 700, these bits are 0x00, which is the value for information packet 700PacketType0XA8 & 0x00 = 0XA8.
SynchSecond704 (1 byte): A value in the range 0..119 that identifies at what second the packet was sent by the server clock. This value would be the offset from the latest even start.
SynchPhase706 (1 byte): The number of slots (0..124) elapsed in sync seconds before sending this packet.
SendProb708 (2 bytes): The number of 16 bits that will be used to calculate the random delay imposed on each outgoing packet. Data packet
FIG. 5 (b) is a graphic depiction of an exemplary data packet 710. The data transmission upstream will be split into such MTU-sized packets, each small enough to be transmitted within a single slot. Downstream data will use the same packet format, but the downstream MTU size will be larger. It will include less than data packets. That is,
PacketType722 (1 byte): A constant that identifies a valid TM packet and identifies which of the four types it is. For the data packet 710, the PacketType value 712 is 0xA9.
ConnID714 (1 byte): Unique connection ID for the virtual socket associated with every virtual connection.
SeqNum716 (1 byte): The value of this field will depend on the position of the packet in the message (see flag field) and will be: That is,
(1) If (IF) this is the first packet in a message and the number of packets is> 1, then this value is the total number of packets in message (1..256) minus 1 (this is the maximum up). The stream message size is 256 * (MTU-4), or 61,440 bytes).
(2) Otherwise (ELSE / IF), if this is the last packet in the message, this value defines the payload size (1..MTU-4) minus 1 of this packet (this is , The receive does not know the actual message size until the last packet is received, but it means that the estimation based on the packet count wastes at most MTU-5 bytes, or 0.39%).
(3) Otherwise (ELSE), this value is the number of packet sequences minus one.
Flag718 (1 byte): A bit vector containing the following bit flags. That is,
FirstPacket: If this is the first packet in the message, set it to (eg = 1).
LastPacket: If this is the last packet in the message, set it to (eg = 1).
Resend: Set to (eg = 1) if this is not the first time this packet has been sent.
Alert: If this is an "alert" message from a server-side source, set it to (eg = 1).
The remaining 4 flag bits will be reserved for future use.
For server-sourced messages (ie alerts), the IP address will be used to identify the STB400. The header space for ConnID614 and SeqNum616 is combined to provide 2 bytes, where the TM server 210 will store the number of ports. This port is then used to identify which virtual connection receives the alert based on the port binding. Alert messages are identified via the Alert bit in Flag field 618. All alert messages must fit within (downstream MTU-5) bytes.
For "minus 1" in the definition of SeqNum616, an exemplary message always consists of 1 and 256 packets, but one byte represents an integer between 0 and 255. Therefore, the SeqNum value 616 is always one less than the value it represents. ACK packet
FIG. 5 (c) is a graphic depiction of an exemplary ACK packet 720. The receipt of data packet 710 will be acknowledged by returning one of these packets. The ACK packet 720 will include: That is,
PacketType722 (1 byte): A constant that identifies a valid TM packet and identifies which of the four types it is. For ACK packet 720, PacketType value 722 is 0xAA.
ConnID724 (1 byte): ConnID value 714 from the received data packet 710.
SoFarCt726 (1 byte): The number of packets of messages received so far before the first missing packet.
ACK bit 728 (1 byte): Acknowledgment of up to 8 packets after packet #SoFarCt. As with all transmitted data, it will be in network byte order with the first packet after SoFarCt acknowledged by the higher bits and the eighth packet after SoFarCt acknowledged by the lower bits.
SendProb729 (2 bytes): The number of 16 bits used to calculate the random delay imposed on each outgoing packet. Probe packet
FIG. 5 (d) is a graphic depiction of an exemplary probe packet 730. Normally, all data packets 710 in a message must contain the maximum transmission unit (MTU-6), except for the last packet. This makes it easy to estimate the packet size. However, when load information is not available, the first packet of the message will need to be sent as a probe to get the load information in the corresponding ACK. The probe packet 730 would preferably be small and fit within a single MAC cell payload (34 bytes). Thus, probe packet 730 contains the same 6 bytes of header information as the first data packet of message 732 without payload (although with PacketType = 0xAB). The SeqNum value 736 counts only subsequent 1-256 data packets and does not count the probe as a packet in any buffer length calculation (see TM Server section for description of further use of probe data in predictive network load). That). TM client data
Figures 6 (a) to 6 (c) describe the structure that would be used in one embodiment of TM Client 420 to support the written API. Those and other data types and variables that will be utilized by TM Client 420 (not depicted in the figure) will be: That is,
(1) As depicted in Figure 6 (a), the virtual socket structure 810 will contain all the information needed to implement a virtual stream socket. This will include state information 812, port binding 813, asynchronous callback information 814, remote host IP 815 and port 816, and information about the current message 817 being processed.
(2) The tm_socket variable will contain the actual datagram socket descriptor and will be bound to the VPORT of the port used to listen for incoming messages. This socket should remain open as long as the client node agent or application (eg, EBIF user agent 410) is active, if possible. Otherwise, the socket will be opened and initialized as needed. Generally, this socket is created via the standard socket API. However, some implementations will provide other socket acquisition APIs.
(3) The send_probability variable will contain a value representing the transmission probability used by vreserve () 606 to schedule packet transmissions via vsend () 612. Rather than expressing the probability as a floating point number (ie, a value between 0 and 1), this value would be more conveniently expressed as the product of the transmission probability and 65,536, rounded up to the nearest integer. .. The value contained in this variable will be sent by TM server 210 in both information 700 and ACK packet 720.
(4) As depicted in Figure 6 (b), the virtual socket table 820 would be a table containing the S virtual socket structure 810 (ie, an array, list, etc.), where S is available. Space-based implementation-specific, but up to 16 according to current embodiments. The socket ID is an index (eg, 1..S or 0..S-1) into this table, such as the ConnID (ie connection ID) fields 714, 724, 734 in the TM packet header. .. The socket ID will also be known as a virtual socket descriptor.
(5) The verrno variable will be used by the TM virtual socket to report the error to the programmer. This variable will be added to the errno variable used by the standard socket API.
(6) As depicted in FIG. 6 (c), the reserved queue 800 would be a reserved array (queue), each identifying a virtual socket 820 with packets to send. Each time a new packet is added to the reserved queue 800 or the first packet in the queue is sent, the time to send the next packet in the queue is calculated and stored in reservation_slot. Let's go. This calculation is given in the definition of reservation_slot below, where current_slot_ID refers to the SlotID at the time of calculation.
(7) The reservation_slot variable will be the SlotID (or equivalent), where the next packet will be sent (see Reservation Queue). The value of reservation_slot must be recalculated each time a new send_probability reaches the client via either ACK720 or information packet 700. reservation_slot = current_slot_ID + (tm_random ()% (131072.0 / send_probability + 0.5))
(8) The time_offset_msec variable will indicate the time offset, which synchronizes the time with the TM server 210 and other client nodes when attached to the internal clock time (GMT) on the client node (eg STB). Let me. Accurate time is required to calculate the SlotID accurately, and for other capabilities that may be required. Guaranteed delivery of messages
The following paragraphs provide further details about one embodiment that implements guaranteed delivery of messages. First, details are provided for vsend () 612 in the context of mode 1, assuming that a reservation already exists for a particular virtual socket and the reserved SlotID has arrived. Then, additional description is made that may be necessary for other modes.
As mentioned above, it is a message (or part) because vsend () 612 is not guaranteed to send the whole message in one call like its BSD socket counterpart or send () 506. Will block until the message) is sent. This would not be a problem with send () 506. However, various embodiments of the invention spread message packets over time to avoid slot collisions, so the application is blocked during many seconds waiting for vsend () 612 to respond. obtain. So if the reserved time for a data packet is long, vsend () 612 will return control to the caller. When not all messages are sent, vsend () 612 will make a reservation for the next vsend () 612 call based on the current send_probability value.
In one exemplary implementation, vsend () 612 decomposes the message into packets of (MTU-5) bytes (or less bytes for the last packet) and is scheduled by vreserve () 606. To send those packets. Processing vsend (vsocket_descriptor, message_ptr, message_length) would occur as follows: That is,
(1) Set data_sent = -1 and set end_count = 0.
(2) Set wait_time = vreserve (vsocket_descriptor).
(3) If (IF), wait_time> VSEND_WASTE, set verrno = VSENDLATER and return data_sent.
(4) If (IF), continue_count> = VSEND_TRIES, set verrno = VMAXRESENDS and return data_sent.
(5) If (IF), wait_time> 0, sleep for a period of wait_time milliseconds, then return to step 2.
(6) If (IF), the message currently in progress to vsocket_descriptor is in the send state, and the message buffer contains message_ptr [message_length], skip to step 8.
(7) Initialize the message progress data for vsocket_descriptor in the virtual socket table (see discussion associated with Figure 6 (b)).
(8) If (IF) all packets of the message have never been sent, build the next packet to send, update the virtual socket structure accordingly, and skip. And proceed to step 11.
(9) If (IF) all transmitted packets have not yet been acknowledged, reconstruct the minimum number of negatively answered packets, set the resume flag bit, and respond accordingly. Update the message structure, increment resume_count, and skip to step 11.
(10) Update the message information of the virtual socket and return message_length.
(11) Wait for the next SLOT boundary and, if necessary, send the (re) reconstructed packet.
(12) Set data_sent = SoFarCt * (MTU-4) and return to step 2.
This definition of vsend () 612 assumes that the receipt of both information 700 and ACK packet 720 is handled via an asynchronous signal interrupt while vsend () 612 is processing. In particular, it assumes that information packet 700 updates send_probability708 and reservation_slot, and that ACK packet 720 updates the ACK bit 728 field in the virtual socket structure 810 defined by SoFarCt726 and ConnID724. Not all data packets need to be acknowledged by the ACK packet 720. In fact, the frequency of ACK720 will be inversely proportional to the rate of change in server load (ie send_probability) and the rate of reception of out-of-sequence packets. Ideally, under light load, the ACK720 would be sent on every fourth received packet. In various embodiments, the only request would be that an ACK packet 720 would have to be generated for both the first and last packets of the message.
In mode 2, nothing has changed above, except that tm_socket is unassigned and bound to the port's VPORT until the virtual socket is opened on vsocket () 602, and information packet 700 to define send_probability708. Will be blocked by vreserve () 606 until is received.
In mode 3, assuming send_probability is the default send probability value, vreserve () 606 and / or vsend () 612 must send probe packet 730 for the message and before proceeding. ACK packet 720 must be received for the probe (providing the actual transmission probability value). Failure to receive ACK720 for this probe before a short timeout (eg 3 seconds) will cause the call to fail and set the appropriate error in verrno. Virtual socket
The following paragraphs further describe one embodiment of the virtual socket implementation.
Traffic management according to various embodiments of the present invention will endeavor to use a single datagram socket (ie, the tm_socket descriptor) to meet the following requirements: That is,
(1) Simulate the effect of multiple stream sockets,
(2) Listen for information packet 700, which is a broadcast from TM server 210, and
(3) Listen for unicast alert messages from the application server to the client node (eg STB400). This is true in all three modes. The only difference is how long the datagram socket is held at the start of listening.
TM client APIs other than vsend () 612 and vrecv () 616 will do nothing with tm_socket. Instead, it will modify the information in the virtual socket table 820 (or reserved queue 800) that is subsequently used when sending or receiving data packets. For example, when an ACK packet 720 or data packet 710 is received, the header field in the packet determines which socket, and thereby which callback function is the recipient of the actual packet. It will be matched with the data in the virtual socket table 820.
The assigned tm_socket is bound to the VPORT (ie 1962) and "listens" for incoming traffic via the signaling mechanism. The packet_type fields 702, 712, 722, 732 of incoming packets are checked both to filter out non-TM packets and to properly handle the various packet types that will be received. Information packet 700 will be handled internally by TM Server 210 and TM Client 420, as disclosed in the Traffic Reporting and Client Clock Synchronization section. The ACK720 and data 710 packets (other than alerts) will contain ConnID fields 714,724 (indexes to the virtual socket table) that identify the virtual socket connection to which the packet belongs. The alert message will be identified by the Flag field bit and Alert, and the ConnID and SeqNum bits are combined to define the number of 2-byte ports, and the virtual socket bound to that number of ports is the recipient of the message. is there.
The TM client 420 will rely on asynchronous I / O signal communication (SIGIO) to call various TM internal routines when there is activity (or error) on the tm_socket socket. For example, a TM asynchronous callback function associated with a virtual socket (via vasynch () 605) would be called by the signal handler.
Various embodiments for sending and receiving data are described in more detail in the guaranteed delivery of the message section. Message data compression
One peculiarity of the cable OOB networking context is that 99% of traffic will consist of HTTP messages. This allows a simple static compression method to generate significant savings. A static table-based scheme will be adopted to compress all messages prior to transport, as well as: Decompression should be concise. char * string [128] = { "HTTP", / * Add other HTTP keywords * / "Content length", / * Add other header strings * / "& Amp;", / * Add other entities * / "Amr", / * Add other IAM keywords * / "\ R \ n", / * Add other common multi-character strings * / / * Requires more than 123 strings * / / * Once all the above strings are defined, a * / / * Fast switch-based lookup mechanism * / / * Can be implemented * / }, static char output [MAX_MSG]; static int outlen; void compress (char * message, int inlen) { int pos, code; outlen = 0; for (pos = 0; pos <inlen; code <0? pos ++: 0) { for (code = 0; code <128; code ++) { if ((code [0] == message [pos]) &&! Strncmp (& (message [pos]), string [code], strlen (string [code])) ) { output [outlen ++] = (char) -code; break; } } } / * The result is'output' with length,'outlen' * / }
This compression scheme is intended not to corrupt binary data. This would also make it suitable for non-HTTP protocols that would not necessarily send text data. Calculate transmission probability
The following paragraphs describe an exemplary method of calculating the transmission probability value.
The interface between the TM server 210 and the bandwidth throttling code, which handles the actual communication with the TM client 420, will be implemented using a single API call, as follows: That is,
int got_packet (int size, int isOutOfOrder)
Every time TM server 420 receives a packet from any client, it should call got_packet () immediately. The size of the packet (ie header + payload) will be passed in the size parameter. If the number of sequences in the packet is not the expected value (ie, the number of previous sequences + 1), then a non-zero (true) value will be passed in isOutOfOrder, otherwise a 0 (false) value. Will be passed with this parameter.
The return value of got_packet () will be either 0 or a positive nonzero integer. If the return value is 0, no further action is required. However, if the value is non-zero, the return value should be used as a new transmission probability and communicated to all TM clients 420 via ACK720 and information packet 700.
In one embodiment, the transmit probability value will be the ratio of the target bandwidth (per HFC node) to the expected bandwidth (per HFC node) for the immediate future. The target bandwidth is simply the configured maximum bandwidth (per HFC node) multiplied by a small regulator (eg, 0.9) to hold the result directly below the maximum. Expected bandwidth is the number of "active" STBs (ie, client nodes) at each HFC node that will send additional packets. This would be estimated as 2 * P / SPold, where P is the calculated mean number of packets received per SLOT and SPold is the value before the transmission probability.
Also, the regulator, K, will be calculated on a regular basis, taking into account system configuration and inaccuracies in occasional transient effects. Broadcast frequency of information packets
The following paragraphs describe an exemplary method of determining the broadcast frequency of information packet 700.
The frequency of occurrence of information packet 700 will be controlled by the return value of got_packet (). A new information packet 700 should be broadcast each time this function returns a nonzero value. Care should be taken to prevent too frequent or pseudo-occurrence of information packet 700 broadcasts.
Specifically, got_packet () will return a non-zero send_probability value to deploy via another info packet broadcast each time: That is,
(a) 10 seconds have passed since the last information packet broadcast, or
(b) Last information packet Information packet 700 At least 0.5 seconds have passed since the broadcast, and out-of-order packets are seen or
(c) At least 0.5 seconds have passed since the last information packet broadcast, and the packet / second rate is on the rise.
Otherwise, got_packet () will return zero (0) and the previous value of send_probability remains valid. Bandwidth throttling simulation
This section presents a simulation description of one embodiment of the bandwidth throttling method according to one embodiment of the present invention. A description of how the simulation was performed is presented along with a description of the results, as depicted in FIGS. 7 (a)-7 (c).
The simulation involves modeling the QPSK network, where the TM server 210 communicates with multiple TM clients 420 over the network. The QPSK network model monitors upstream and downstream throughput and drops packets in either direction that exceed the bandwidth limit.
As throughput approaches the theoretical bandwidth limit, the probability of packet loss approaches 1. The theoretical maximum packet throughput upstream is (1 / e) * 256,000bps = 94,000bps, and the total size of all upstream packets (including TM header and 28-byte UDP / IP header) is S bytes (or s). Assuming = S * 8 bits), then the probability of the next lost (and completely ignored) packet is given as Ppacket_loss (s) = (s / 94,000). Programmatically, the following IF conditions test this. That is, If (if) ((tm_random ()% 94000) <s), then { ; / * Packets are lost * / } Otherwise (else) { ; / * Process packets * / }
In the simulation results depicted in Figures 7 (a) to 7 (c), a large (configurable) number of STB400s and HFC nodes 300 are used for each second of the configurable test period (where set to 1 hour). Was simulated for all 125 SLOTs.
Figure 7 (a) is a graph depicting a simulation of a network load without bandwidth throttling, where the raw bandwidth load (per HFC node 300) averages at each second of the 1-hour simulation. Be transformed.
Figure 7 (b) is a graph depicting a simulation of a network load with bandwidth throttling, where the HFC node 300 is exposed to the same raw bandwidth traffic as in Figure 7 (a). It is configured for a maximum of 40 Kbps per hit. The average traffic load is limited here at 40 Kbps, and the period of high load is several seconds longer in each case.
Figure 7 (c) is a graph depicting the difference between simulated network loads with and without bandwidth throttling. This graph overlays the previous two graphs and includes a line showing the 60-second operating average for bandwidth-managed traffic. This line shows the beneficial effects of bandwidth throttling embodiments of various embodiments of the invention, as described herein.
Examples or parts of the embodiments disclosed herein are for dedicated purpose computers, computer systems with microcomputers, minicons, or mainframes such as programmed microprocessors, microcontrollers, peripherals. Integrated circuit elements, CSICs (customer-only integrated circuits) or ASICs (application-only integrated circuits) or other integrated circuits, logic circuits, digital signal processors, programmable logic devices such as FPGAs, PLDs, PLAs or PALs, or the present specification. It will utilize any of a variety of technologies, including any other device or device deployment that can carry out any step of the process described in the document.
A set of instructions (eg, computer software) that make up a computer operating system to perform any of the operations described herein may, upon request, be contained in either a variety of media or media. It should be understood that it will be. In addition, any data processed by a series of instructions will also be contained in either a variety of media or media. That is, the special medium used to hold a set of instructions (eg, memory) or the data used in the examples described herein may be, for example, in any of various physical forms or transmissions. Will present. Illustratively, the medium is a compact disc, DVD, integrated circuit, hard disk, floppy disk, optical disk, magnetic tape, RAM, ROM, PROM, EPROM, wiring, cable, fiber, communication channel, satellite transmission or other remote. It will be in the form of a source of data that will be transmitted and read by any other medium or computer.
The various components described herein, such as executable computer software running on a computer, will be installed remotely and communicate with each other via electronic transmission over one or more computer networks. What will be done should also be understood. As mentioned herein, networks are not limited, but are such as wide area networks (WANs), local area networks (LANs), global networks such as the Internet, public telephone exchange networks, etc. It will include telephone networks, wireless communication networks, mobile phone networks, intranets, etc., or any combination thereof. In various embodiments, the network will include one or any number of exemplary types of networks described above, operating as stand-alone networks or in cooperation with each other. The use of the term network herein is not intended to limit the network to a single network.
It will be readily appreciated by those skilled in the art that the present invention is sensitive to a wide range of practicalities and applications. Many embodiments and applications of the invention other than those described herein, as well as many modifications, modifications and equivalent arrangements, without departing from the essence or scope of the invention, the invention and its aforementioned. The description will be clear or reasonably suggested.
Although the previous statements exemplify and describe embodiments of the present invention, it should be understood that the present invention is not limited to the configurations disclosed herein. The present invention can be embodied in other particular forms without departing from its spiritual or essential attributes.
16 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15 Sheet 16
Every citation, both waysCites: the store holds 3 of 4
| Document | Relation | Office |
|---|---|---|
| JP2003298604A | Cites | Japan |
| JP2010283759A | Cites | Japan |
| US20090070468A1 | Cites | United States of America |
| 百名 盛久 Morihisa Momona,CATVアクセスネットワークにおける技術課題と標準化動向 Technologies and Standardization Activities in Cable TV Access Networks,電子情報通信学会技術研究報告 Vol.98 No.589 IEICE Technical Report,日本,社団法人電子情報通信学会 The Institute of Electronics,Information and Communication Engineers,第98巻,第57-64頁 | Non-patent | – |
14 members in 6 offices
Priority claims9
| Document | Office | Kind | Date |
|---|---|---|---|
| 201161551203 | United States of America | P | |
| 201161551203 | United States of America | P | |
| 61551203 | United States of America | – | |
| 2012061844 | United States of America | W | |
| 2012061844 | United States of America | W | |
| 61551203 | – | – | – |
| US201161551203P | – | – | – |
| US2012061844 | – | – | – |
| WO2012US61844 | – | – | – |
Members14
| Document | Office | Kind | |
|---|---|---|---|
| US2013100810A1 | United States of America | A1 | |
| CA2851825A1 | Canada | A1 | |
| WO2013063218A1 | World Intellectual Property Organization (WIPO) | A1 | |
| KR20140091019A | Republic of Korea | A | |
| EP2772020A1 | European Patent Office (EPO) | A1 | |
| JP2014531179A | Japan | A | |
| US8937866B2 | United States of America | B2 | |
| EP2772020A4 | European Patent Office (EPO) | A4 | |
| US2015207707A1 | United States of America | A1 | |
| JP5982002B2This record | Japan | B2 | |
| US9577899B2 | United States of America | B2 | |
| KR101973590B1 | Republic of Korea | B1 | |
| CA2851825C | Canada | C | |
| EP2772020B1 | European Patent Office (EPO) | B1 |
15 legal events, as the office reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | |
|---|---|---|
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Certificate of patent or registration of utility modelJAPANESE INTERMEDIATE CODE: R150R150 | R150 | |
| First payment of annual fees (during grant procedure)JAPANESE INTERMEDIATE CODE: A61A61 | A61 | |
| Written decision to grant a patent or to grant a registration (utility model)JAPANESE INTERMEDIATE CODE: A01A01 | A01 | |
| Decision of grant or rejection writtenTRDD | TRDD | |
| Written submission of copy of amendment under article 19 pctJAPANESE INTERMEDIATE CODE: A524A524 | A524 | |
| Notification of reasons for refusalJAPANESE INTERMEDIATE CODE: A131A131 | A131 | |
| Report on retrievalJAPANESE INTERMEDIATE CODE: A971007A977 | A977 | |
| Written request for application examinationJAPANESE INTERMEDIATE CODE: A621A621 | A621 |
Numbers
- Publication
- 5982002
- Publication, DOCDB
- 5982002
- Publication, EPODOC
- JP5982002B
- Application
- 2014538989
- Application, DOCDB
- 2014538989
- Application, EPODOC
- JP20140538989
Titles2
- Japanese
- トラフィックスケジューリングを使用したネットワーク帯域幅調整
- English
- Network bandwidth throttling using traffic scheduling
Classification
- CPC, 11
- H04L43/0882
- H04L41/147
- H04L47/12
- H04L47/801
- H04L47/822
- H04L47/781
- H04L47/83
- H04L41/0896
- H04L43/062
- H04L47/196
- H04L47/28
- IPC, 5
- H04L47 2475
- H04L47 52
- H04L47 80
- H04L12 859
- H04L12 911
