International Business Machines Corporation

Rajendran Rajan

Sanjay Damodar Kamat

Roch A Guerin

Dinesh C Verma

Arvind Krishna

Vinod Gerard Peris

Edward James Ellesson

Gary Scott Delp

Philip Lynn Leichty

Charles Steven Lingafelt

Subir Varma

Partha P Bhattacharya

Albert Alfonse Slane

Leo Temoshenko

John Handley Shaffer

Leonidas Georgiadis

Walter Cade Metz

Bret Elliott Harrison

Earl Hardin Booth

David Richard Poulter

Charles Bruce Dillon

Victor Firoiu

Vinod Gerard John Peris

Saswati Sarkar

Ping P Pan

A method, apparatus, computer product and structure is presented for representing and managing large amounts of information concerning networks of elements. While being useful for communication networks, it can be also usefully deployed in the context of other networks such as distribution and transportation networks. The method uses a hierarchical construct called 'catalog'&#x2014;a set of elements (which could be 'atomic' elements or catalogs themselves)&#x2014;to organize information about physical or abstract entities relevant for modeling the network. A matrix construct whose rows and columns constitute such elements are used to model connections at different levels of abstraction. A common framework and representation provided using these two constructs is shown to be useful for visualization, administration, configuration, modeling, monitoring and manipulation of the network.

Representing, configuring, administering, monitoring, and/or modeling connections using catalogs and matrixes

An apparatus, a search tree structure, methods and computer devices for constructing and using the structure to efficiently accomplish policy based service differentiation in packet networks is presented. This invention reduces the number of steps performed to implement packet classification. It uses a method of preprocessing a given set of policy rules by modeling the conditions in the rules as multidimensional hyper-cubes, a simple and compact search tree is constructed. Using this search tree, packet classification is achieved determining all applicable policies for a packet with a few compare and branch instructions.

Search tree for policy based packet classification in communication networks

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

The present invention is an apparatus for controlling client node access to data items maintained in a storage device. The data items include volatile data items. The apparatus comprises a communication device for communicating with multiple client nodes; and a processor, coupled to the storage device for polling the client nodes to exchange (e.g., retrieve and/or transmit) data related to the volatile data items, via the communication device. The processing system further controls client node access to the data items of the storage device. In this way, the apparatus and method of the present invention remedies the problems associated with directory server overload.

Active polling by network LDAP directory

The present invention is a directory server for monitoring network access requests, which includes a storage device for storing data items and an identifier associated with a monitoring node for at least a selected data item of the data items; a communication device for transmitting signals to the monitoring node; and a processing device, coupled to the storage device and the communication device. The processing device receives a network access request for the selected data item and, responsive to receipt of the request, automatically transmits a signal notifying the monitoring node of the request via the communication device, thereby enabling the monitoring node, e.g., a third party, to enforce traffic class priorities and access characteristics of the network.

Third-party notification by network directory server

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.

Growing community of inventors

Bronx, NY, United States of America

Rajendran Rajan