Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-05-28
2002-10-15
Patel, Ajit (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S417000, C710S052000
Reexamination Certificate
active
06466579
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of hardware and software for computer network communications, and more specifically to the field of buffering the data involved in network connections, particularly in asynchronous transfer mode (ATM) switches or any other fast network environment.
2. Description of the Background Art
Network communication systems interconnect many users in a network. Each user is connected to the network at a port. The network is formed by the interconnection of many nodes where information input at an input port from one user at a source is passed from node to node through the network to an output port and to another user at a destination. The information transferred from source to destination is packetized and each node switches incoming packets at incoming ports to outgoing packets at outgoing ports.
Fast packet switches at the nodes may transfer hundreds of thousands of packets per second at every switch port. Switch sizes range from a few ports to thousands of ports. The term “fast packet switch” includes switches capable of handling both variable-length packets and fixed-length packets. Fixed-length packets are desirable since they simplify the switch design. Fast packet switches using short, fixed-length packets (cells) are referred to as asynchronous transfer mode (ATM) switches. Fast packet switches handle different types of communications services in a single integrated network where such services may include voice, video and data communications. Since voice and video services can tolerate only a limited amount of delay and delay variance through a network, ATM switches are especially suitable for such services. The ATM standard for broadband networks defines a cell having a length of 53 bytes with a header of 5 bytes and data of 48 bytes.
In a typical ATM switch, the cell processing functions are performed within the nodes of a network. Each node is an ATM switch, which includes input controllers, a switch fabric, output controllers and a node control. The node control is used for functions including connection establishment and release, bandwidth reservation, congestion control, maintenance and network management.
Cell arrivals in an ATM switch are not scheduled. Typically, a number of cells may arrive simultaneously at different input ports each requesting the same output port. Operations in which requests exceeding the output capacity of the output port are referred to as output contention (or conflict). Since an output port can only transmit a fixed number of cells at a time, only the fixed number of cells can be accepted for transmission, so that any other cells routed to that port must either be discarded or buffered in a queue. When the traffic load exceeds the available system resources at a switch, connections are refused, performance degrades, and congestion results.
Congestion can be brought about by several factors. If nodes in a network are too slow to perform the various tasks required of them (queuing-buffers, updating tables, etc.), queues build up, even though excess line capacity exists. If a node does not have sufficient buffer resource to support the estimated load of a pending call, the node will block the call. One available congestion control technique to address this problem is that of preallocating resources. When a channel is set up (commonly referred to as a “virtual” channel, since the set up is only planned until the data is actually forwarded), a call request travels through the network making table entries at each node that controls the route to be followed by subsequent traffic. In preallocating, each call request reserves one or more data buffers in each node unless all the buffers are already reserved. If all buffers are reserved, another route is found or a “busy signal” is returned to the source. If buffers are reserved for each channel in each node, there is always a place to store any incoming packet to that node. One problem with preallocation is that substantial buffer resources are allocated to specific virtual channel connections, regardless of whether there is any traffic over the virtual channel. An inefficient use of resources results, particularly for buffer resources, since resources not being used by the connection to which they are allocated are nevertheless unavailable to other virtual channels.
This problem is exacerbated in ATM networks due to the required data type characteristics. The ATM Forum Traffic Management Specification, version 4.0 [ATMF96b, af-tm-0056.000, April, 1996, incorporated herein by reference), defines five service categories: Constant Bit Rate (“CBR”), Variable Bit Rate realtime (“VBRrt”), Variable Bit Rate non-realtime (“VBRnrt”), Unspecified Bit Rate (“UBR”), and Available Bit Rate (“ABR”).
The CBR service category, which resembles leased-line services, is used for connections needing a static amount of bandwidth continuously throughout the connection. CBR is characterized by its Peak Cell Rate (PCR). Typical applications include voice and video, including videoconferencing and audio/video distribution and retrieval (television, distance learning, pay-per-view, video-on-demand, and audio library). CBR uses a static amount of bandwidth continuously throughout the life of the connection.
The VBRrt service category supplies tightly constrained delay and delay variation, but not necessarily a fixed transmission rate. VBRrt connections are characterized by their PCR, Sustained Cell Rate (SCR), and Maximum Burst Size (MBS). Applications include native ATM voice with bandwidth compression and silence suppression, and some types of multimedia communications.
The VBRnrt service category is intended for non-realtime bursty traffic that requires service guarantees, such as frame relay traffic. Like VBRrt, VBRnrt connections are also characterized in terms of PCR, SCR and MBS. Typical applications include loss-sensitive/delay-insensitive transaction processing (airline reservations, banking transactions, process monitoring) and frame relay internetworking.
The UBR service category, sometimes referred to as a best-effort service, is intended for non-realtime, bursty applications. These include text, data, and image transfer, which are tolerant to delay and loss, including telecommuting, email, and supercomputer applications such as remote procedure calls, distributed file services, and computer process swapping and paging. Other examples include LAN emulation and applications such as LAN interconnecting and internetworking—which run over router-based protocols like Transmission Control Protocol/Internet
The ABR service category provides a Minimum Cell Rate (MCR) plus any available bandwidth. ABR connections are characterized by both a PCR and an MCR, and are used by applications that can adapt to network feedback. A flow-control mechanism fairly allocates the available bandwidth among ABR connections. Applications are similar to those for UBR. ABR traffic is supplied an MCR and any available bandwidth, while UBR traffic does not require that switches use specified cell rates in negotiating bandwidth.
At all times, but of particular import during periods of congestion, switching priority is given to the “guaranteed” data types, including CBR, VBRrt, VBRnrt, and ABR (but only ABR below the MCR), while UBR and the remaining ABR traffic (above the MCR) gets access only to remaining available (“non-guaranteed”) bandwidth after guaranteed connection contracts are fulfilled. When sufficient buffer resources are unavailable, the ATM switch will block pending connections.
Such specific constraints on traffic flow, priority, and timing result in a need for a system which determines how large queues should be allowed to grow (per-connection) within the shared buffer. Queue lengths for delay-sensitive traffic (CBR and VBRrt) should be tightly constrained in order to bound worst-case delay. Conversely, queue lengths for delay-insensitive traffic (VBRnrt, ABR, UBR) should be allowed to grow to be very large, if necessary, i
Cavasian Edward G.
Scott James P.
Network Equipment Technologies Inc.
Patel Ajit
Townsend and Townsend / and Crew LLP
LandOfFree
Bi-modal control system and method for partitioning a shared... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bi-modal control system and method for partitioning a shared..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bi-modal control system and method for partitioning a shared... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2996218