International Business Machines Corporation

International Business Corporation

Roch A Guerin

Rajendran Rajan

Leonidas Georgiadis

Israel Cidon

Levent Gun

Vinod Gerard Peris

Jeffrey Haskell Derby

Gerald Arnold Marin

Inder Sarat Gopal

Hamid Ahmadi

Yuval Y Shavitt

Andrew E Slater

Dinesh C Verma

Gary Scott Delp

Subir Varma

Marcia Lambert Peters

Marc Adam Kaplan

Mihir M Bellare

Kenneth Harvey Potter, Jr

Gerald Lebizay

Gary Roy Shippy

John E Drake, Jr

Philip Lynn Leichty

Arvind Krishna

Raif O Onvural

Yeong-Chang L Lien

Phillip W Rogaway

John G Dudley

Ling-Ching W Tai

Sanjay Damodar Kamat

Caglan M Aras

Kumar N Sivarajan

Vinod Gerard John Peris

Paul S Chang

James Thomas Rayfield

Albert Alfonse Slane

Mahmoud Naghshineh

Jeane S Chen

John Handley Shaffer

Chee-Seng Chow

Theodore E Tedijanto

Edward James Ellesson

David Richard Poulter

Alexander Birman

Victor Firoiu

Ping P Pan

Anthony M Lee

Khosrow Sohraby

Jeffrey, H Derby

Abhay Kumar Parekh

Ilias Iliadis

Teofilo C Ancheta

Pao-Chi Chang

A method of controlling packet traffic in an IP network of originating, receiving and intermediate nodes to meet performance objectives established by service level agreements. Traffic statistics and performance data such as delay and loss rates relating to traffic flows are collected at intermediate nodes. A control server processes the collected data to determines data flow rates for different priorities of traffic. A static directory node is used to look up inter-node connections and determine initial traffic classes corresponding to those connections. The rates are combined with the initial traffic classes to define codes for encoding the headers of packets to determine their network priority.

Architecture for supporting service level agreements in an IP network

A method of providing a rate guarantee to individual or groups of flows in a router through intelligent management of buffers. Rate guarantees are provided by intelligently allocating and isolating the buffers available to each flow. In its most basic form, the method applies to output queued network devices with a simple FIFO scheduler, where a number of streams some with rate reservations are sought to be multiplexed onto an outgoing link. The method involves strictly partitioning the buffer into portions strictly reserved for each flow in proportion to its link reservation. This ensures that each stream obtains the link reservation rate in a scalable manner. A particular embodiment of the invention allow for a portion of the buffer to be strictly partitioned while allowing streams full access to the remainder of the buffer. Other embodiments utilize the use of a link scheduler to divide bandwidth amongst a number of queues, while using buffer management to facilitate bandwidth amongst a number of flows in each queue.

Rate guarantees through buffer management

A method, apparatus and system is provided by which two or more cooperating end-users of the Internet and/or other network can dynamically select and use a single Internet or other network service provider (ISP) from among a multitude of ISPs based on the application requirements. The service provider may be selected in a dynamic fashion. This overcomes the problem wherein traditionally most end-users, whether they are individuals or organizations, are connected to the Internet or other network through a single Internet and/or other network service provider. However, users generally may have more than a single connection to the Internet and/or other network. In such cases the routing of traffic over these multiple connections is handled by IP routers based on the routing information that they exchange with their peers. This information is relatively static in nature and is typically based on the state of links that interconnect the different routers. The invention provides a mechanism for the end-user to take advantage of different rates or services that might be provided by competing Internet and/or other network service providers. Furthermore, there are cases where the choice of which provider to use depends on the application. Thus this invention enables cooperating users (or sites of an organization) to dynamically select different providers on an application by application basis.

Dynamic selection of network providers

A method and apparatus are provided for scheduling the transmission of cells of a plurality of data streams in a communications network. An earliest deadline first (EDF) scheduler is provided for scheduling the transmission of cells of a plurality of data streams in a communications network to ensure that the connection or data stream with the earliest deadline is transmitted first. Each of the multiple data streams has a delay bound or deadline. Data of each data stream is enqueued to a corresponding data cell queue. A timing wheel time slot based on an identified target transmission time for each data cell queue is calculated utilizing an addition of a maximum delay value. A move forward timing mechanism includes a scan forward feature to identify a succession of virtual connection or data stream cell queues for transmission. A multiple tier cell scheduler is provided that includes at least two scheduling timing wheels. The priority of a first timing wheel is higher than the priority of a second timing wheel. The priority of the second timing wheel is higher than the priority of an optional third timing wheel. The third timing wheel includes a best effort operational mode. The relative rates between data streams are maintained, while the absolute rates of the data streams are increased or decreased in the lowest priority wheel.

Earliest deadline first communications cell scheduler and scheduling

A method and apparatus are provided for resource allocation with guarantees. A resource allocator is coupled to a controller. The resource allocator allocates resources between a plurality of arrival processes. A dedicated resource pool and a shared resource pool are provided. When an arrival process is identified, the resource allocator obtains a predefined characterizing value for the identified arrival process. Responsive to the obtained predefined characterizing value, resource from one of the dedicated resource pool or the shared resource pool is allocated to the arrival process. The controller is utilized for tracking resource use and for providing the predefined characterizing value for each of the plurality of arrival processes. The dedicated resource pool has a predetermined capacity greater than or equal to the total of all the low threshold values for each of the arrival processes. The dedicated resource pool provides the guarantees with the shared pool providing statistical multiplexed resource use. The controller increments a usage charge for the arrival process when a resource is allocated and decrements the usage charge at the end of use of the allocated resource. The controller evaluates use for the identified arrival process and updates the predefined characterizing value.

Method and apparatus for resource allocation with guarantees

The present invention addresses the issue of controlling delay variations (jitter) in packet-switched networks by enhancing the capabilities of existing scheduling policies. The idea is to use a few bits in the header of packets to send jitter control information to the downstream network elements, so that the delay variation caused by the upstream network element, is compensated for by the downstream network element. The key point to observe is that packets (or cells in ATM) may be small, and therefore, not contain many bits in the header that can be used for jitter control. We describe a unique scheme, that utilizes the bits that are available for jitter control in an efficient manner, allowing for the desired jitter to be obtained with as few bits as possible.

Method to control jitter in high-speed packet-switched networks

A polling procedure providing the capabilities to assign and dynamically modify a user's communication parameters (i.e., response allocation and polling rate) based on the user's bandwidth requirements. In addition, the polling procedure instructs the users to delay their responses as a function of round-trip propagation delay and remaining response allocation for previously polled users to ensure that poll responses from separate users do not overlap.

Method and system for an efficient multiple access polling protocol for

A distance learning system consists of a plurality of multi-cast clients of various classes and priorities with one multi-cast client as a primary multi-cast client, a multi-cast server, arbitrator and a distance learning session coordinator. The primary multi-cast client provides the default or primary Audio-Visual Material (AVM) stream. The Multi-Cast Server (MCS) setups a multi-cast over a point to multi-point connection which connects all multi-cast clients that are to take part in a particular distance learning session, along with the Primary multi-cast client. Additionally, the primary multi-cast client is connected to the MCS via a point-to-point link. The multi-cast clients and the primary multi-cast client receive an AVM material stream from the multi-cast server via the point to multi-point connection. When a multi-cast client wishes to speak, a speaking request is sent to the arbitrator, the arbitrator determines whether to grant or deny the speaking request. If permission is granted then a point-to-point link is established between the requesting multi-cast client and the MCS. The requesting multi-cast client then provides an AVM stream to the multi-cast server over the newly established point-to-point connection and the multi-cast server switches or provides the AVM stream associated with the requesting multi-cast Client over the point to multi-point connection. When the requesting multi-cast client is through speaking the MCS switches the AVM stream associated with the primary multi-cast client onto the point to multi-point connection and the point-to-point link with the requesting multi-cast client is terminated.

Method and apparatus for multi-cast based video conferencing

Method system and article of manufacture for multi-casting audio visual

A leaky bucket checker which combines synchronous updates with event driven asynchronous updates triggered by packet arrivals. A synchronous update is performed exactly as an event-driven update by assuming that a packet of length zero has arrived at the time of the update. These updates are performed in a round robin fashion on each connection. Therefore, assuming that one such update can be performed in each clock tick, the maximum bit representation of the last update time state variable can be limited to N bits for 2.sup.N total connections. Given the reduced processing and storage costs, a great number of network connections and leaky bucket checkers is possible.

Method and system for implementing multiple leaky bucket checkers using

The present invention relates to the issue of providing end-to-end delay guarantees in a multi-node communication system. More specifically, the present invention addresses the problem of specifying operational parameters of rate-controlled service disciplines in a communication network in order to efficiently provide end-to-end delay guarantees. The key contribution is a method for specifying leaky bucket parameters as well as scheduling delays at each node, which are used as inputs to the rate-controlled service discipline.

Traffic flow regulation to guarantee end-to-end delay in packet switched

A method and system for providing data authentication, within a data communication environment, in a manner which is simple, fast, and provably secure. A data message to be sent is partitioned into data blocks. Each data block is combined with a block index to create a word. A pseudo-random function is applied to each word to create a plurality of enciphered data strings. An identifying header, comprising the identity of the sender and a counter value, is also enciphered using a pseudo-random function. These enciphered data strings and header are logically combined to create a tag. As the enciphering of a particular word occurs independent of the other words, each block can be enciphered independently of the others. The method and system can thus be performed and structured in either a parallel or pipelined fashion. A receiving component or system generates a second tag which can then be compared with the transmitted tag to determine message authentication.

Method and apparatus for data authentication in a data communication

Switching apparatus and method for multiple traffic classes

A non-quota access indicator is circulated among nodes in a multi-node quota based communication system with a shared resource, indicating maximum possible non-quota access to the shared resource to a given node receiving same. Upon arrival at a node, the indicator is saved and then updated to reflect the current status of that node as either starved or satisfied, the former being a condition of currently having quota remaining and a shared resource access requirement, and the latter being a condition of either currently having no remaining quota or having no current shared resource access requirement. After updating, the node immediately propagates the indicator to the next node in the system. When a node without quota requires access to the shared resource, it compares its requirement to the last stored indicator and accesses the shared resource if the stored indicator is equal to or greater than the access requirement.

Method and apparatus for improved throughput in a multi-node

Growing community of inventors

Yorktown Heights, NY, United States of America

Roch A Guerin