Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-11-24
2001-05-15
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S429000
Reexamination Certificate
active
06233243
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to telecommunications networks and more particularly to a method and apparatus for performing virtual circuit merging in a connection based network.
In a connection based network, such as an Asynchronous Transfer Mode (ATM) network, packets are transmitted over virtual connections or circuits. Virtual circuits are established at call setup between a packet source and a packet destination. In the ATM environment, the Virtual Connections are defined by Virtual Path Identifier (VPI) and a Virtual Connection Identifier (VCI) fields within the ATM cell header.
Since ATM networks are connection-oriented, carrying connectionless traffic such as that based upon the Internet Protocol (IP) is problematic. Several methods exist for the routing of such information within an ATM network. The simplest form of mapping involves the assignment of a unique virtual circuit for each source and destination pair at the network switch. This technique, however, leads to the proliferation of connections or virtual circuits at each switch and results in large buffer requirements for connection identifier lookup tables in each network switch. Additionally, such an assignment technique is computationally intensive as a result of the need to process voluminous connection setup and tear down requests.
Various techniques have been proposed to minimize the need to establish a unique connection for each source destination pair. In one technique, known as Virtual Path merging, the Virtual Path (VPI) address labels, are used to identify the destination of the packet and all packets being forwarded to the same destination employ the same VPI. The Virtual Connection Identifier is employed to identify the packet source. Thus, in a network employing VP merging, a recipient of cells arriving over a single virtual path can identify the sender and reconstruct the packets even if the cells are interleaved. This technique, however, has a significant limitation. Since the Virtual Path Identifier field in the ATM cell header comprises a 12 bit field at the network to network interface, only 4096 Virtual Paths can be supported. The assignment of a single Virtual Path per destination, irrespective of the number of connections associated with the Virtual Path, is undesirably limiting with regard to the number of destinations that may be supported in the network. Thus, VP merging is typically wasteful of virtual connection assignments.
Virtual connection merging is a technique for forwarding all packets destined for the same destination address over the same VPI/VCI address. In order for the destination to successfully delineate packets from different sources, the cells comprising a packet must not be interleaved over the virtual connection. Accordingly, packets are typically assembled in a buffer on an egress Input Output (I/O) Module of a switch and are not scheduled for transmission until an End of Packet (EOP) indication is received. Only after all cells comprising a packet have been assembled in an egress I/O module buffer and an EOP received, is the packet scheduled for transmission over the respective Virtual Connection.
While the above described VC merging technique avoids problems introduced by the interleaving of cells of different packets, it has certain disadvantages. First, as a consequence of the need to fully buffer all packets prior to transmission in a store and forward manner and the fact that the packets may be variably sized, the reassembly buffers need to be quite large. Additionally, undesirable delays occur because the packet must be reassembled at each intermediate network node between the source and the destination. Each time the packet is reassembled, additional delays may be introduced.
It would therefore be desirable to be able to perform Virtual Connection (VC) merging while minimizing the aforementioned problems associated with prior VC merging techniques.
BRIEF SUMMARY OF THE INVENTION
A method and apparatus for performing virtual circuit merging in the egress port of a network switch is disclosed. Cells belonging to different packets are associated with a unique connection identifier (CID) upon arrival at an ingress port of the network switch. The connection identifiers (CIDs) for respective VPI/VCI addresses are assigned within the network switch at call setup as an administrative function. An identification of CIDs identifying packets to be merged over a single virtual circuit are associated with a single group identifier (GID) within the switch. If a packet associated with a GID has been fully received it is scheduled for transmission and transmission of the packet is initiated. If no packets associated with the GID have been completely assembled but one or more packets have been partially received, a partially received packet is identified in accordance with a predetermined selection technique and cut-through transmission of the selected packet from the network switch is initiated prior to the completion of reception and reassembly of the packet.
At the time the transmission of the partially received packet is initiated a timer is started. If the timer expires prior to receipt of an end of packet (EOP) indicator for the packet in transit, an EOP indicator is transmitted from the output port over the merged connection and the balance of the incoming packet is disregarded. In the above described manner, buffering requirements at the egress port and undesirable delays resulting from the need to schedule a packet only after it has been completely received are avoided.
REFERENCES:
patent: 4737953 (1988-04-01), Koch et al.
patent: 5307345 (1994-04-01), Lozowick et al.
patent: 5379296 (1995-01-01), Johnson et al.
patent: 5434864 (1995-07-01), Perlman et al.
patent: 5440691 (1995-08-01), Carrafiello et al.
patent: 5465331 (1995-11-01), Yang et al.
patent: 5471472 (1995-11-01), McClure et al.
patent: 5477547 (1995-12-01), Sugiyama
patent: 5481540 (1996-01-01), Huang
patent: 5483640 (1996-01-01), Isfeld et al.
patent: 5502726 (1996-03-01), Fischer
patent: 5598581 (1997-01-01), Daines et al.
patent: 5651002 (1997-07-01), Van Seters et al.
patent: 5805816 (1998-09-01), Picazo, Jr. et al.
ATM Forum: Technical Working Group; Title: Performance Issues in Vc-Merge Capable Switches for IP Over ATM, Indra Widjaja et al.; Date: Jul. 21-25, 1997; pp 1-18.
EtherSwitch® EPS-1500 (brochure) by Kalpana The EtherSwitch Company; Date: Sep. 1993.
EtherSwitch® Ethernet Packet Processor (brochure) by Kalpana, The Parallel Networking Company; Date: Unknown.
Switch.NLM v1.0-SW2000 (brochure) by Kalpana, The EtherSwitch Company; Date: Mar. 1994.
Tehranipour, Aby, Lester Lipsky; A Comparison of Three Switching Schemes in Isotropic Networks with Noisy Channels; IEEE Transaction on Telecommunications, vol. 41 No. 5 pp. 782-792, May 1993.*
Petr, David W., Camerin Braun, Rasheda Rabi; Delay Performance of Segmentation Options for Mixed Packet Networks; IEEE; pp. 84-88, Jan. 1994.*
Shin, Kang G., Stuart W. Daniel; Analysis and Implementation of Hybrid Switching; ISCA; pp. 211-219, Jun. 1995.*
Grossglauser, Matthias, K.K. Ramakrishnan; SEAM Scalable and Efficient ATM Multicast; IEEE; pp. 867-875, Apr. 1997.
Ganmukhi Mahesh N.
Palnati Prasasth R.
Ascend Communications, Inc.
Kwoh Jasper
Nguyen Chau
Weingarten, Schurgin Gagnebin & Hayes LLP
LandOfFree
Method and apparatus for performing cut-through virtual... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing cut-through virtual..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing cut-through virtual... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2551867