Connectionless Network for Routing Cells With Connectionless Address, VPI and Packet-Identifying VCI

1. Field of the Invention

The present invention relates generally to data communication networks, and more specifically to an ATM (asynchronous transfer mode) connectionless data communication network.

2. Description of the Related Art

In an ATM network, a user packet is segmented at the entry point of the network into a plurality of 53-byte cells each having a 5-byte cell header and a 48-byte payload field. According to the ITU-T Recommendation I.363, the cells at the beginning and the end of the packet are designated as BOM (beginning of message) and EOM (end of message) cells, respectively, and those between these cells are designated as COM (continuation of message) cells. At the exit point of the network, the cells are reassembled into a packet for delivery to the destination.

In an ATM connectionless network, the user message is a single-packet message, known as a datagram. The cell header of the cells that comprise a datagram contains a destination address (DA) field into which the destination of the packet is inserted. Japanese Laid-Open Patent Specification Hei 5-260077 discloses an ATM connectionless data communication system. According to this specification, each node of the network has a DA-RDA translation table in which destination addresses are mapped to reduced destination addresses which are compressed versions of the destination addresses. When the cells of a datagram (packet) are routed from one node to the next, the DA field of each cell is used to search the DA-RDA table for a corresponding reduced destination address. The DA field of the cell is updated with this reduced destination address and the cell is routed according to its DA field. However, if a number of packets from different sources are sent to the same destination, the same destination address will be written into the DA field of the cells from these sources. If these cells exist simultaneously on a communication link of the network, the destination is incapable of discriminating the respective sources of the arriving cells and fails to reassemble them into packets according to their sources.

Therefore, the prior art technique cannot apply to ATM connectionless networks where a number of packets are likely to exist simultaneously on a communication link.

It is therefore an object of the present invention to provide an ATM connectionless data communication system that allows packets of different sources to be uniquely distinguished from each other even if they are destined for the same address.

According to a first aspect of the present invention, there is provided a data communication system for a plurality of user end systems. The communications system comprises an asynchronous transfer mode network having a plurality of connecting points at the periphery of the network. In the network, a packet from the user end systems is segmented into a plurality of cells containing a connectionless address designating one of the connecting points, a VPI designating one of a plurality of permanent virtual connections, and a virtual channel identifier (VCI) identifying the packet. The cells having VCIs of the same value are routed through a permanent virtual connection designated by the VPI contained in the cells toward a destination connecting point designated by the connectionless address contained in the cells. The VPI and VCI of the cells are rewritten when the cells are routed via a further permanent virtual connection until the destination connecting point is reached. At the destination connecting point, the cells having VCIs of the same value are reassembled into a packet and transmitted to one of the user end systems.

According to a second aspect, the present invention provides a data communication system comprising a plurality of interworking units for accommodating local area networks, the interworking units segmenting a packet received from the local area networks into a plurality of cells for transmission to an asynchronous transfer mode (ATM) network, the cells containing a connectionless address designating a destination local area network, a virtual path identifier (VPI) designating a permanent virtual connection, and a virtual channel identifier (VCI) identifying the packet. The ATM network comprises a plurality of cross-connect nodes interconnected by communication links. The cross-connect nodes establish a plurality of permanent virtual connections between the interworking units and the nodes and between the nodes in pairs, receive the cells from the interworking units and route the cells having VCIs of the same value through the permanent virtual connections to a destination interworking unit according to the connectionless address and the VPI contained in the cells. The destination interworking unit assembles the cells having VCIs of the same value into a packet for routing the packet to the destination local area network according to the connection address transmitted by the packet.

The present invention will be described in further detail with reference to the accompanying drawings, in which:

FIG. 1 is a block diagram of an ATM connectionless data communication network embodying the present invention;

FIG. 2 is a diagrammatic view of the signal formats used in the present invention;

FIG. 3 is a block diagram of an interworking unit according to the present invention;

FIG. 4 is a block diagram of a connectionless cross-connect node of the present invention;

FIG. 5 is an illustration of the VCI status table of FIG. 4;

FIG. 6 is a block diagram of a modified VCI generator; and

FIG. 7 is a block diagram of another modification of the VCI generator.

Referring now to FIG. 1, there is shown an ATM (asynchronous transfer mode) connectionless data communication network according to the present invention. The network comprises a plurality of connectionless cross-connect (CLXC) nodes 11 and an address resolution server 13, all of which are interconnected by communication links 14. User end systems such as local area networks (LANs) 15 are connected to the network via interworking units 12 which perform translation between LAN's packets (i.e., Ethernet packets) and network's ATM cells. All point-to-point connections between source and destination nodes 11, between interworking units 12 and network nodes 11 and between interworking units 12 and the address resolution server 13, are established as virtual paths, or permanent virtual connections (PVC). The connecting point between each LAN and the associated interworking unit is identified by a unique connectionless address. In the address resolution server 13 holds a table in which IP addresses of all LAN's hosts and connectionless addresses of all interworking units are mapped. If a source interworking unit is not aware of the connectionless address of a destination interworking unit, it will send a request to the address resolution server 13 to obtain the connectionless address of the destination unit. The connectionless network may also be implemented with existing ATM cross-connect systems and ATM self-routine switches.

As shown in FIG. 2, when a host of a LAN sends a connectionless data, a destination host outside of the LAN, the data will be a single-message packet such as an IP datagram containing a source IP address (SA) and a destination IP address (DA) followed by a user data field. If the shortest distance to the destination is via the connectionless cross-connect network, the IP datagram is encapsulated between a header and a trailer (frame check sequence) and forwarded from the LAN as an Ethernet packet to the associated interworking unit. The Ethernet packet header contains the MAC (medium access control sublayer) address of the source interworking unit in the destination address (DA) field and the MAC address of the source host in the source address (SA) field. In the specification, the term "packet" is used throughout to designate user's connectionless data.

As illustrated in FIG. 3, each interworking unit 12 has a LAN interface unit 20 where an Ethernet packet from the associated LAN is decapsulated and an original IP datagram (see also FIG. 2) is extracted and supplied to a CLNIP (connectionless network interface protocol) packet encapsulation circuit 21. Encapsulation circuit 21 looks up the SA field of the IP datagram and determines from which LAN it has received the packet and inserts the connectionless address of the interworking unit into the source address (SA) field of a CLNIP packet header (FIG. 2).

An address resolution table 22 is provided in the interworking unit, where IP addresses have been mapped to connectionless addresses of the network, using an address resolution protocol. Packet encapsulation circuit 21 then uses the DA field of the IP datagram as an address pointer to search through the address resolution table 22 for a corresponding destination connectionless address that identifies the connecting point between the destination interworking unit and the destination LAN. If the destination connectionless address is found in the address resolution table 22, it is inserted into the DA field of the CLNIP packet header. Otherwise, encapsulation circuit 21 will create a request packet and forward it to the address resolution server 13 as described above to obtain the destination connectionless address and updates the address resolution table 22. The decapsulated IP datagram is then inserted into the data (payload) field of the CLNIP packet and forwarded from encapsulation circuit 21 to an AAL (ATM adaptation layer) frame encapsulation circuit 23 for conversion to an AAL frame.

The AAL encapsulation circuit 23 encapsulates the CLNIP packet between a CPCS (common part convergence sublayer) header and a CPCS trailer of the AAL layer to form a CPCS-PDU (protocol data unit) packet and presents to a cell segmentation circuit 24 for segmentation into ATM cells. Note that, in the case of AAL layer 5, no header is appended to the packet. The header of each ATM cell has a segment type (ST) field and a payload type (PT) field. If the AAL layer is an AAL-3 or AAL-4 layer, the segment type field is used to establish the identity of a cell, indicating whether it is a BOM (beginning-of-message) cell, a COM (continuation-of-message) cell, or an EOM (end-of-message) cell. If the AAL layer is an AAL-5 layer, it is only the EOM cell that is identified by the payload type (PT) field of the cell header. There are no explicit fields to identify the BOM and COM cells in the case of the AAL-5 layer. All ATM cells that comprise a single AAL frame are consistently assigned a virtual channel identifier (VCI) of the same bit pattern. A virtual path identifier (VPI) is assigned to the permanent virtual connection between the interworking unit and the associated CLXC node. This VPI is also assigned at the interworking unit to the ATM cells destined for the same connectionless address. The assigned VPI and VCI are inserted into the VPI/VCI field of the cell header by a VPI/VCI insertion circuit 25.

According to one embodiment of the present invention, VCIs are generated by a counter 26 connected to the segmentation circuit 24. Counter 26 produces a binary count value in response to an output of the segmentation circuit 24 indicating the beginning of a message (either CLNIP packet or AAL frame) and supplies this count value to the VPI/VCI insertion circuit 25 as a VCI for all the cells of a packet. Since this count value is incremented only at the beginning of a packet, the cells of each packet can be distinguished from those of other packets. The output of the VPI/VCI insertion circuit 25 is then forwarded through an interface 27 to the associated cross-connect node and propagated through the network with no possibility that the integrity of cell sequence within the same packet will be lost.

As shown in FIG. 4, each connectionless cross-connect node of the network comprises a plurality of incoming link circuits 41 connected to incoming links through an interface 40, a plurality of outgoing link circuits 61 connected to outgoing links through an interface 65, and a switch 50 connected between the incoming link circuits 41 and the outgoing link circuits 61.

ATM cells arriving from the associated interworking unit or from other cross-connect nodes are applied to one of the incoming link circuits 41. The incoming cells are also applied to an AAL handler 43 and a buffer 47. AAL handler 43 monitors each SAR-PDU header to detect its VCI and monitors the ST (segment type) field if AAL layer 3/4 is used or the PT (payload type) field if AAL layer 5 is used to determine the relative position of each ATM cell. AAL handler 43 produces a write-0 command signal when an EOM cell is detected. This write-0 command signal is applied to a VCI status table 42 in which busy/idle states of all VCIs are stored in locations addressable by the detected VCI as clearly shown in FIG. 5. The busy/idle states of each VCI are represented respectively by binary 1 indicating that the VCI is being used for the cells of a particular AAL frame and binary 0 indicating that the VCI is idle.

The application of the write-0 command signal to the table 42 causes a binary 0 to be written into a storage location identified by the detected VCI so that the VCI in that location is marked as being idle. When the AAL handler 43 detects a cell other than EOM, it supplies a read command signal to the VCI status table 42 to read the busy/idle status of a storage location specified by the detected VCI. An idle bit detector 44 is connected to the VCI status table 42 to determine whether the content of the VCI-specified location of table 42 is an idle bit. If an idle status bit is stored in the VCI-specified location, idle bit detector 44 recognizes that the currently received cell is a BOM cell and applies a write-1 command signal to the VCI status table 42 to mark the VCI-specified location as busy, or assigned.

The output of the idle bit detector 44 is also applied to a routing circuit 45 as a beginning-of-message indication. If the VCI-specific location is indicated as being assigned, the idle bit detector 44 recognizes that the currently received cell is a COM (continuation-of-message) cell and produces no output signal.

AAL handler 43 assembles ATM cells into a CLNIP packet and extracts the connectionless address from the DA field of the packet and supplies it to the routing circuit 45. Routing circuit 45 produces a routing signal according to the connectionless address and the VCI from AAL handler 43 when a BOM indication is given from the idle bit detector 44. The routing signal for cells of each CLNIP packet is retained until the AAL handler 43 detects the EOM cell of the packet.

The routing signal from each incoming link circuit 41 is supplied to a switch controller 51 which controls the switch 50 to establish a connection between the incoming link circuit and one of the outgoing link circuits 61.

If a frame header comprises a number of cells, AAL handler 43 control the buffer 46 so that, when the BOM cell of the header is stored in buffer 46, it is held in queue only for a duration corresponding to that number of cells. That is, the BOM cell only has to wait for the arrival of the COM cell that defines the end of the header. When these header cells are stored in buffer 46, the routing circuit 45 is informed by AAL handler 43 of the destination connectionless address of the frame and its VPI and VCI values and produces and holds a routing signal of the frame until it is informed of the detection of an EOM cell having the same VCI value. Therefore, the amount of memory required to implement the buffer 46 is determined by the maximum length of the frame header.

Each outgoing link circuit 61 comprises a VPI/VCI insertion circuit 62, a BOM detector 63 and a counter 64. Counter 64 is incremented by the output of BOM detector 63 when it detects the beginning of a message (packet) and supplies this count value as a new VCI to be assigned to all cells of the same packet supplied from the switch 50. The VPI, which is assigned to the permanent virtual connection between the current node and a destination node, is also assigned to these cells as a new VPI. The VPI/VCI field in the header of each cell is updated with the newly assigned VPI and VCI values in the VPI/VCI insertion circuit 62 and forwarded to an outgoing link through an interface 65.

It is seen that the VCI field of each cell is updated when it is forwarded from one node to the next.

Reverting to FIG. 3, ATM cells arriving from the associated cross-connect node at a destination interworking unit are coupled through interface 27 to a header error check circuit 30. If no error is detected in the cell headers, the incoming ATM cells are supplied to a CLNIP packet reassembly circuit 31. The ATM cells from the error check circuit are also applied to an AAL handler 33.

AAL handler 33 monitors each ATM cell and detects the VCI of the cell. AAL handler 33 further monitors the ST (segment type) field of each SAR-PDU header if AAL layer 3/4 is used or the PT (payload type) field of each cell if AAL layer 5 is used and produces a write-0 command signal when an EOM cell is detected. This write-0 command signal is applied to a VCI status table 32 which is similar to that shown in FIG. 5 in which the busy/idle states of VCIs are stored in locations addressable by the VCI of the received cell detected by the handler 33.

The busy/idle states of each VCI are represented respectively by binary 1 and binary 0. The application of the write-0 command to the table 32 causes a binary 0 to be written into a storage location of the table 32 specified by the detected VCI so that the VCI in this location is marked as being idle. When the AAL handler 33 detects is cell other than EOM, it supplies a read command signal to the VCI status table 32 to read the busy/idle status of a storage location specified by the detected VCI. An idle bit detector 34 is connected to the VCI status table 32 to determine whether the content of the VCI-specified location of table 32 is an idle bit. If an idle status bit is stored in the VCI-specified location, idle bit detector 34 recognizes that the currently received cell is a BOM cell and applies a write-1 command signal to the VCI status table 32 to mark the VCI-specified location as busy. The output of the idle bit detector 34 is also applied to a buffer controller 35 as a beginning-of-message indication. If a busy indication bit is stored in the VCI-specified location, the idle bit detector 34 recognizes that the currently received cell is a COM cell and produces no output signal. After receiving each ATM cell, the AAL handler 33 removes the header of the cell and forwards the 48-byte payload of the cell to a packet buffer 36.

Buffer controller 35 produces an address code indicating CLNIP packet and its storage location within buffer 36 by using the VCI detected by the AAL handler 33 and the BOM indication. Therefore, all ATM cells from the connectionless network are stored in queues respectively corresponding to packets. When the AAL handler 33 detects the EOM cell in a CLNIP packet, buffer controller 35 is informed of this fact and knows that this packet has been reassembled in buffer 36 and forwards it to interface 20.

Interface 20 removes the header and trailer of the CLNIP packet and converts the IP datagram in the payload field of the packet to an Ethernet packet and forwards it to one of the user LANs through a port identified by the destination connectionless address contained in the removed CLNIP packet header.

Since the counter 26 of the interworking unit and the counter 64 of the node produce a VCI as a sequence number, there is a possibility that the same VCI is used simultaneously by two packets if the previous packet is held in a long queue prior to transmission. The VCI value of each packet is unique to each link on which it is propagated. Therefore, on each link cells of each packet can be uniquely identified by their VCI. However, since the number of VCIs that can be used for a link is related to its transmission capacity, the likelihood of such possibility increases with an increase in traffic. While the use of a counter for producing VCIs is favorable because of its simple and yet low-cost implementation, it is not suitable for applications where efficient utilization of VCIs is desired for increased traffic.

FIG. 6 illustrates a VCI generator capable of efficient utilization of VCIs. In this modification, a BOM (beginning of message) indication is supplied to a binary counter 70 via an OR gate 71 to increment its count and further to a VCI status memory 72 as a read command signal. The output of counter 70 is supplied as an address pointer to the memory 72 for reading the idle/busy status bit of a location of the memory specified by the address pointer. The output of memory 72 is checked by a status detector 73, which supplied a write-1 command signal to the memory if the status bit is "0" (idle) and supplies a read command signal to the memory and an increment command to the counter via OR gate 71 if the status bit is "1" (busy). As long as the status bit of a storage location is "1", the search for an idle VCI is continued by successively reading other locations of the memory and checking their contents by status detector 73. If the status bit of a location is "0", a gate 74 is activated to pass the output of counter 70 to the VPI/VCI insertion circuit 25 (62) as an assigned VIC and a "0" is written into this location. A buffer 75 is connected to the output of VPI/VCI insertion circuit 25 (62) for absorbing cells waiting for transmission to the link. A VCI detector 76, connected to the output of buffer 75, monitors the cells delivered to the link for detecting the VCI of an EOM cell. When the VCI of an EOM cell is forwarded from buffer 75, the detector 72 detects and uses this VCI as an address pointer for accessing the VCI status memory 72 and supplies a write-0 command signal to the memory to change the status this VCI to "0".

Another modification of the VCI generator, illustrated in FIG. 7, has a first-in-first-out (FIFO) memory 80 in which a plurality of VCI values are initially stored as idle VCIs. A buffer 81, connected to the output of VPI/VCI insertion circuit 25 (62), absorbs ATM cells waiting for transmission. A VCI detector 82 monitors the output of buffer 82 for detecting the VCI of an EOM cell. Upon detecting the VCI of an EOM cell, the detector 82 returns this VCI to the FIFO memory 80 by applying to it a write command signal.