========================================================================= ATM Forum / 97-0504 PROJECT: The ATM Forum Technical Committee ***************************************************************************** SOURCE: Jean Calvignac Patrick Droz IBM Networking Hardware Division IBM Zurich Research Laboratory 30 Saw Mill River Road, 8803 Rueschlikon, Hawthorne, New York 10532 Switzerland jean.calvigna@vnet.ibm.com dro@zurich.ibm.com Claude Basso Doug Dykeman IBM Networking Hardware Division IBM Zurich Research Laboratory Le Plan du Bois, 8803 Rueschlikon, 06610 La Gaude, France Switzerland basso@vnet.ibm.com ddy@zurich.ibm.com ***************************************************************************** TITLE: Dynamic IDentifier Assignment (DIDA) for Merged ATM Connections ***************************************************************************** DATE: July 20-25, 1997 (Montreal, Canada) ***************************************************************************** DISTRIBUTION: PNNI SWG ***************************************************************************** ABSTRACT: This contribution describes Dynamic IDentifier Assignment (DIDA) for Merged ATM Connections. DIDA provides a method for combining traffic from multiple senders on a single ATM connection without requiring reassembly at intermediate switches or use of globally coordinated identifiers. DIDA connections are established by an extended version of the Q.2931 protocol. The DIDA method also provides a natural means for performing Early Packet Discard (EPD) function on the merged traffic at intermediate switches. The DIDA method assigns a locally unique identifier to each frame as the cells of the frame transit a switch. This identifier is placed in the VCI field of each cell so that the frame can be identified at the next switch by reference to the VCI value and the arriving port. ***************************************************************************** NOTICE: This contribution has been prepared to assist the ATM Forum. It is offered to the Forum as a basis for discussion and is not a binding proposal on IBM Corp. The statements are subject to change in form and content after further study. Specifically, IBM Corp. reserves the right to add to, amend or modify the statements contained herein. ***************************************************************************** 1. Introduction ---------------- A recent Forum submission [HEIN] describes the use of ATM multipoint-to-point connections to support the interconnection of routers across an ATM network. A key motivation for merged connections is facilitating pairwise interconnection of N routers using N multipoint-to-point connections rather than N-squared point-to-point connections. A key environment for such merged connections is AAL5/UBR. This discussion assumes the AAL5/UBR environment but the proposal may later be extended to other environments. When traffic is merged on a multipoint-to-point connection, cells belonging to frames from different senders may interleave on the connection. A method is required so that the receiver can properly associate cells with frames. This document describes a Dynamic IDentifier Assignment (DIDA) method to provide this association. DIDA does not add latency to ATM traffic in switching nodes where it is implemented and it does not require additional protocols among the switching nodes. DIDA is not implemented at the sending end user and is optional at the receiving end user. Thus, change to the UNI or end user function is not required. DIDA additionally provides a natural method to perform Early Packet Discard (EPD) on the merged connection. In the sections that follow we provide an overview of merge alternatives and describe the DIDA method. 2. Merge Alternatives Overview ------------------------------- Merge schemes can be broadly classed as Frame-Based or Cell-Based. In the case of Frame-Based Merge, cells associated with a frame are transmitted contiguously on outbound ports. This function may be accomplished at each switch by performing AAL5 reassembly followed by AAL5 segmentation. Alternatively, the switch can queue cells belonging to a frame until all cells have been received, and then retransmit the cells so the cells of a frame are contiguous on the outbound port. The latter method can be called pseudo-reassembly. The term 'reassembly' is used generically to refer to either method in this document. Frame-Based Merge offers the advantage that merged connections are indistinguishable from non-merged connections from the perspective of the receiver. Frame-Based Merge requires modification of switches to perform the reassembly function and sufficient memory to buffer frames undergoing reassembly. It also introduces latency greater than that associated with cell relay. In the case of Cell-Based Merge, cells associated with frames from different senders are interleaved on links. An identifier is required so that cells belonging to a frame can be associated with that frame at the receiver. Cell-Based schemes can be classed as Static or Dynamic. In Static schemes, the frame identifier is associated with the sender of the frame. The assignment of identifier to sender is relatively long-lived. The assignment can be established by manual definition, distributed assignment protocol, signaling, or other means. In Dynamic schemes, the frame identifier is associated with individual frames and is relatively short-lived. In the DIDA scheme, for example, a new identifier assignment is made for each frame as the calls of that frame pass through a switch. merge alternatives | | | | cell based frame based | | | | static dynamic 3. Static Cell-Based Merge --------------------------- Before describing the DIDA proposal for Dynamic Cell-Based Merge, it is useful to review two methods of Static Cell-Based Merge. 1. Globally Unique VCI with VP Switching. 2. Distinct VCCs Merged at the Receiver. In the first alternative, the merged connection is a multipoint-to-point VP connection. Each sender is assigned a globally unique identifier having the format of a VCI. The identifier is carried in the VCI field of the ATM cell. A key advantage of this scheme is that no VCC resources are required in the switching nodes as only VP switching is performed. Some disadvantages are: - need for a 'global VCI uniqueness' protocol or manual configuration - limitation of 4096 on the number of merged connections passing across any port (assuming ability to switch on full 12 bits of VPI) - limitation of 256 on the number of merged connections in which a sender can participate (assuming 8-bit VPI at sender UNI) - requirement for some means to identify individual frames for Early Packet Discard at intermediate switches The second method, Distinct VCCs Merged at the Receiver, avoids the requirement for globally unique identifiers. Frames are identified for reassembly by VPI/VCI at the receiver. There is a distinct VCC from each sender to the receiver. Any Traffic Management performed by the switch for VCCs will continue to function in this environment. When the Distinct VCC method is used, there is a VCC corresponding to each sender-receiver pair. In an environment with N senders and receivers, O(N-squared) connection table entries are required by switches. In the worst-case of a port representing a cut-point in the network, N-squared connection table entries are required for the port. Switches generally provide a limited number VCC table entries so the requirement for O(N-squared) VCCs may pose a significant problem. When using either of these methods, a receiving end user must associate a set of VPI/VCI values with the merged connection. The merged connection does not appear to be a single VCC from the perspective of the receiving end user. Reassembly can be performed at the egress switch in order to avoid this problem. 4. Dynamic IDentifier Assignment --------------------------------- In this section we describe a specific Dynamic Cell-Based Merge scheme called Dynamic IDentifier Assignment (DIDA). In this scheme, a value identifies all cells of a specific frame. The value is assigned locally at each switch and the assignment lasts only during the time between reception of the first cell of a frame and transmission of the last cell of that frame at a particular switch. The identifier value has the format of a VCI and is placed in the VCI field of the cell header when the cell is transmitted downstream. At any point in time, the number of active identifier assignments within a switch is equal to the number of frames in transit through that switch. This number is likely to be small relative to the number of senders. 4.1 Details of Merged Connections --------------------------------- DIDA uses ATM multipoint-to-point VP connections. Such connections can be viewed as conventional point-to-multipoint connections with the direction of data flow reversed. As described in [DRAK], Q.2931 signaling can be extended to establish multipoint-to-point VPCs. Conventional ATM traffic arrives at a leaf node of the DIDA mpt-to-pt VPC via conventional VCCs. Traffic from these VCCs is switched to the DIDA VPC. This is the Ingress Point of the DIDA connection. At Intermediate Points along the DIDA connection, traffic from inbound DIDA VP links is switched to the outbound DIDA VP link. At the root of the DIDA VPC, traffic from inbound DIDA VP links is switched to an outbound conventional VCC. This is the Egress Point of the DIDA VPC. In order to prevent the interleaving of cells on the outbound VCC, it is necessary to perform frame reassembly at the DIDA Egress. This is the only point along the path of the DIDA VPC where reassembly is required. To summarize, traffic enters the DIDA VPC via one or more conventional VCCs, is transported by VP switching within the DIDA VPC, and exits the DIDA VPC merged on a conventional VCC. Traffic sent from an individual end user across the UNI is assumed to carry conventional non-merged VCC traffic. The earliest opportunity for merging occurs at the first switch in the data path. For this reason, the sending end user does not have DIDA awareness and uses a standard UNI. The DIDA VP may extend to the receiving end user. In this case, the end user must provide the DIDA function of switching traffic from DIDA VP to conventional VCC. By providing this function at the receiving end user, it is possible to avoid any reassembly function, and associated latency, at other nodes along the path of the DIDA merged connection. Alternatively, the switch upstream from the receiving end user may serve as the DIDA Egress. In this case, the switch performs reassembly so that the receiving end user need not have any DIDA awareness. The end user receives merged traffic on a conventional VCC and the receiving UNI is preserved. In the most general case, a multipoint-to-point connection may have portions implemented using DIDA VPCs and other portions implemented using conventional VC connections where reassembly has been performed prior to transmission. Those portions of the merged connection not using the DIDA VP will incur the additional latency and cost of reassembly. Nodes on both ends of a DIDA VP link must implement DIDA functionality. Example 1: +----+ A-----| | +----+ B-----| X |=====| | C-----| | | | ----- conventional VCC +----+ | | | Z |=====J ===== DIDA VPC +----+ | | D-----| | | | E-----| Y |=====| | In this example, A-F are sending F-----| | +----+ end users and J is the receiving +----+ end user. Reassembly is performed only at J. Example 2: +----+ A-----| | +----+ B-----| X |=====| | C-----| | | | ----- conventional VCC +----+ | | | Z |-----J ===== DIDA VPC +----+ | | D-----| | | | E-----| Y |=====| | In this example, A-F are sending F-----| | +----+ end users and J is the receiving +----+ end user. Reassembly is performed at switch Z which is the DIDA Egress. Reassembly is also performed as usual at J. Example 3: +----+ A-----| | +----+ B-----| W |-----| | C-----| | | | ----- conventional VCC +----+ | | | Z |-----J ===== DIDA VPC +----+ | | D-----| | | | E-----| X |=====| | In this example, A-I are sending F-----| | | | end users and J is the receiving +----+ | | end user. Reassembly is performed | | at switch Z which is the DIDA Egress +----+ | | AND at switch W which does not have G-----| | | | DIDA capabilities. Reassembly is also H-----| Y |=====| | Performed as usual at the receiving I-----| | +----+ end user J. The path from A to J +----+ will impose greater latency than the path from D to J. Nodes performing DIDA and nodes performing reassembly can cooperate to form a single mpt-to-pt connection supporting merged traffic. The network may also contain mpt-to-pt VP connections implementing static cell-based merged. These connections can co-exist in the same switch in 'ships-in-the-night' mode. In this section, it has been described how traffic is switched along the path of a multipoint-to-point ATM connection. When the traffic is carried within a DIDA VP connection, cells associated with frames from different senders will be interleaved on the connection. It is necessary to provide a method of identifying the cells belonging to a frame, so that reassembly can be performed at the DIDA Egress. This method is described in the next section. It is important to note that the method of switching and the method of frame identification are orthogonal activities, although both are required to implement a DIDA merged connection. 4.2 Details of Dynamic IDentifier Assignment -------------------------------------------- The Dynamic IDentifier Assignment activities described in this section are assumed to occur after inbound switching activities but before outbound switching activities. During merged connection establishment, the switch retains certain information about the connection. This includes identification of the connection as a DIDA merged connection and the node's role as Ingress Point, Egress Point, or Interior Point. When it is determined that an an arriving cell is associated with a DIDA merged connection, a Frame_Table, associated with the inbound port, is searched to determine whether a Frame_Information_Element (FIE) has been assigned to the frame. The FIE can be identified by an ID value carried in the VCI field of inbound cells of the frame. An exception occurs at the DIDA Ingress, where the FIE is associated with the connection table entry of the inbound VCC. If no FIE is found to be associated with an arriving cell, then the cell is assumed to be the first cell of a frame, and a FIE is assigned to that frame. When a FIE is assigned to an inbound frame, an ID value is removed from a list of Free_ID values and is placed in the FIE. The Free_ID list is global to the node. The ID value will be written in the VCI field of each cell of the frame when it is transmitted downstream. When an arriving cell is marked with end-of-frame, the ID value from the FIE is written to the VCI field as usual, but the association between the FIE and the frame is ended and the ID value is returned to the Free_ID list. When the node is a DIDA Egress, frames are reassembled, using the inbound ID values as the means to identify frames. In summary, a Frame Information Element (FIE) is associated with the cells of a frame between the time that the first cell of the frame is received and the last cell of the frame is transmitted. During its existence, the FIE contains a number, unique within the node, that is written in the VCI field of each cell of the frame as it is transmitted downstream. The FIE associated with a cell is identified by the inbound port and the ID value found in the VCI field of the arriving cell. At the Ingress Point, the FIE is identified by the inbound VCC table entry. At the Egress point, no outbound ID value is assigned, but the inbound ID values are used to delineate frames for reassembly. It is key to the DIDA concept that ID values are assigned from a global pool at each node. This insures that the downstream node can uniquely identify frames by arriving port and inbound VCI value. It is possible that an end-of-frame cell will be lost. In this case, the FIE is not released after transmission of the partial frame. Some subsequent frame will reuse the ID contained in the FIE. The result at the receiver is that one frame from each of two different senders will be lost. This is not very different from the usual case of end-of-frame cell loss, in which case two frames from the same sender will be lost. In the general case, the dynamic ID value varies from frame to frame, but there is no requirement that the ID values associated with two frames in sequence must be different. Also note that the receiver cannot identify the sender by the ID value. The value is only a means of distinguishing cells associated with different frames. In environments where sender identification is needed, it is assumed that such information is conveyed by higher layers. The logic and data structures required by DIDA are similar in kind to those generally required for standard ATM switching. This suggests that the switch modifications implied by the DIDA method are not extensive. 4.3 Dynamic IDentifier Assignment Logic --------------------------------------- The logic described in the previous section is summarized in the following algorithm: IF Connection_Type is DIDA THEN IF Ingress_Point THEN locate FIE identified by VC connection table entry ELSE search Frame_Table for FIE using PN.VCI as key ENDIF IF no_FIE_exists THEN get ID from Free_ID list write ID value to FIE IF Ingress_Point THEN associate FIE with VC connection table entry ELSE place FIE in Frame_Table using inbound PN.VCI as key ENDIF ENDIF IF Egress_Point THEN queue cells to FIE ELSE write outbound ID to VCI field of cell transmit cell ENDIF IF inbound cell is end_of_frame THEN IF Egress_Point then transmit queued cells on egress VCC ENDIF IF Ingress_Point THEN disassociate FIE from VC connection table entry ELSE remove FIE from Frame_Table ENDIF return ID to Free_ID list ENDIF ENDIF 4.4 Frame_Table Structure ------------------------- The description in the previous section does not specify the structure of the Frame_Table. It must be possible to perform Frame_Table lookup rapidly in switching hardware. One reasonable structure is a table that can be indexed by the value of the inbound ID. The number of table entries, and therefore the size of the required memory, can be small as the number of IDs need only be equal to the number of frames concurrently in transit through the upstream switch. 4.5 Dynamic ID Assignment Example ----------------------------------- In the example below, nodes A, B, C, D, and E are senders associated with a merged connection. Node F is the receiver. Each link between sender and Ingress Point is a VCC and is marked with an appropriate VPI.VCI value established during enhanced Q.2931 signaling. The link between the Egress Point S3 and receiver F is also a VCC and is marked with a VPI.VCI value assigned by extended Q.2931 signaling. A cell received on P1 of S1, from sender A, undergoes VC-to-VP switching at S1, where it is determined that the outbound VPI value is 9, and the cell is to be forwarded on P3 of S1. The outbound VCI value of 57 is supplied by Dynamic VCI Assignment in S1. The cell from sender A therefore carries VPI.VCI = 9.57 on the link S1-S3. The cell received on P2 of S3, originally from sender A, undergoes VP switching, with the inbound VPI = 9 changed to the outbound VPI = 8 and the outbound port is determined to be P4. The VCI field is overwritten with the Dynamic VCI value 82. The cell from sender A therefore carries VPI.VCI = 8.82 on the link S3-S4. The cell received on P1 of S4, originally from sender A, undergoes reassembly and VP-to-VC switching. The cell is forwarded via P4 on VPI.VCI 7.62. 3.49 P1 ______ E A ----------| | |2.64 | | | | S1 | |P1 6.52 | |P3 9.57(A) P2 __|___ ______ B ----------| |==============| | | | P2|______| 9.41(B) | |P4 P1| |P2 | S3 |=========| S4 |--------F 12.38 P1 ______ P3 P3| | 8.82(A) | |7.62(A,D,E) C ----------| |==============| | 8.47(D) | | | | 6.49(D) |______| 8.98(E) |______| | S2 | 9.35 | | D ----------| | P2|______| 4.6. DIDA and Early Packet Discard ----------------------------------------------------- In the UBR environment, cells are discarded when congestion occurs. In such cases, it is efficient to discard all cells of a frame when any cells of the frame are to be discarded. This requires a decision at the time of processing the first cell of the frame as to whether all cells are to be dropped. This function is known as Early Packet Discard (EPD). On conventional VC connections, state information is associated with the VCC so that all cells of a frame can be dropped from start-of-frame to end-of-frame. When merging UBR traffic on VP connections, however, the state information must be associated with individual frames rather than the VPC. Switching logic for VP connections generally does not provide this function. Dynamic ID Assignment provides a natural method for performing EPD on a VPC. The FIE containing the ID associated with the frame is marked with an indication as to whether cells associated with the frame are to be dropped. 4.7. Distinct Dynamic ID on Upside and Downside ----------------------------------------------------- The description thus far has assumed that DIDA is applied at the level of the entire switching node. In practice, switches may be designed as a set of switch adaptors interconnected via a switch fabric. Each such adaptor has some number of ports. Two switching decisions are made when a cell arrives at a switching node. The inbound adaptor determines the identity of the outbound adaptor to which the cell is forwarded via the switching fabric and the outbound adaptor determines the identity of the physical port on which the cell is to be transmitted. Cell discard may occur at either of these switching points. It is therefore desirable to provide the Early Packet Discard function at both points. Applying DIDA at the adaptor level has other advantages. The size of the frame-table on each adaptor can be smaller as it requires entries only for local ports. The scheme works at the adaptor level much as it does at the switch level. On the inbound adaptor, we perform the Frame_Table lookup based on inbound PN.VCI. In the case of adaptor-level DIDA, the PN is locally unique to the inbound adaptor. ID assignment is made from a pool of ID values that is global to the adaptor. On the outbound adaptor we perform the Frame_Table lookup based on the inbound adaptor number and VCI value. The logical path through the switch fabric from inbound adaptor to outbound adaptor, can be viewed as a port from the perspective of the outbound adaptor. Again, ID assignment is made from a pool that is global to the adaptor. This method assumes that the switch fabric can carry the identity of the inbound adaptor to the outbound adaptor. It is significant that DIDA can be applied at the level of the individual adaptor. A key advantage of DIDA is that it provides a natural way to support EPD on the merged connection. If it is desirable to perform EPD on both inbound and outbound adaptors, then it is important that the scheme works at the adaptor level. 5. Comparing Merge Alternatives --------------------------------- A. pseudo-reassembly (Frame-Based Merge) + No difference between merged and non-merged traffic from perspective of receiver + Early Packet Discard provided simply - Large storage requirement for frame reassembly - Latency introduced as cells are queued until they can be transmitted contiguously - Implies a significant extension of switch function comment: this may be a useful function to provide at the network boundary so that receiving nodes can receive traffic on merged connections exactly as they would on non-merged connections. B. 1. Globally Unique VCI with VP Switching. + Intermediate switches have no awareness of individual senders, significantly reducing storage requirements + No switch modification + Easy scheme to implement in software if VCI values are user configured and no EPD is provided - Requires method of unique global VCI assignment - Does not provide Early Packet Discard unless switching hardware supports this function on VP connections - Number of merged VP connections passing across any port limited to 4096 - Number of VP merged connections limited to 256 if sender is attached via UNI. comment: if switching hardware does not provide Early Packet Discard for the VP, this solution may be of limited value. C. 2. Distinct VCCs Merged at the Receiver. + No requirement for globally unique VCI + No switch modification + Provides Early Packet Discard if the switch provides this function on VC connections - Requires O(N-squared) connection table entries comment: the N-squared problem makes this solution infeasible in many environments. D. Dynamic ID Assignment + ID assignments exist only while a frame is in transit, resulting in small storage requirement + No requirement for globally unique VCI + natural method for Early Packet Discard on merged VP + Switch extension similar to existing switch logic - Some switch modification is required - Number of merged connections passing across any port limited to 4096 6. Merging on Reserved Bandwidth Connections -------------------------------------------- This document describes the use of DIDA for the merging of UBR traffic as would be the case when IP routers are interconnected via an ATM network. DIDA may also be useful in providing merged connections with QoS requirements as would be the case when RSVP traffic is carried on an ATM network. Details of such a proposal are for further study. 7. Proposals ------------ A. It is proposed that the PNNI specification be include (1)extensions to Q.2931 signaling required to establish DIDA VP connections and (2)transport requirements between DIDA nodes interconnected via PNNI. B. It is proposed that the UNI specification be extended to include (1)extensions to Q.2931 signaling required to establish DIDA VP connections and (2)transport requirements between a DIDA Egress Switch and the receiving end user. 8. Conclusions -------------- Dynamic ID Assignment provides a method of merging with a relatively small storage and signaling requirement. It does not impact the latency of ATM traffic and allows a natural method for Early Packet Discard on the merged connection. No global VCI assignment protocol is required. The switch extension is similar to logic already implemented in ATM switches. The method of Frame-Based Merge (reassembly) may be useful at the network boundary where there may be a requirement to present merged traffic to the receiver on a single VCC, or in at other places in the network. The reassembly and DIDA methods can be combined in a single mpt-to-pt connection. The methods of Static Cell-Based Merge are suitable for initial 'software only' implementations. The VC switching solution is limited with respect to the number of connections that can be supported. The VP switching solution may be limited by the absence of Early Packet Discard function on the merged VP. DIDA can coexist in "ships in the night" mode with both of the Static Cell-Based Merge methods. It is proposed that DIDA function be standardized at the UNI and PNNI. 9. References -------------- [HEIN] Juha Heinanen "Multipoint-to-point VCs", ATM Forum draft 97-0261, 1997. [DRAK] John Drake and Joel Halpern "VC Merge Support Using Standard Signaling and Routing", ATM Forum draft 97-0428, 1997