WO2001033780A1

WO2001033780A1 - A method for handling resources in a digital time division multiplexed communication network

Info

Publication number: WO2001033780A1
Application number: PCT/SE2000/002107
Authority: WO
Inventors: Johan Ageby; Christer Bohm
Original assignee: Net Insight AB
Current assignee: Net Insight AB
Priority date: 1999-11-05
Filing date: 2000-10-27
Publication date: 2001-05-10
Anticipated expiration: 2002-05-05
Also published as: AU1563501A; SE9904025L; SE9904025D0

Abstract

A method for handling resources in a digital time-division multiplexed communication network, which network comprises nodes on a link. The nodes can have ownership of time slots, and can borrow and lend time slots. One node on said link is operative to control distribution changes of time slot ownership on behalf of two or more nodes on the link, while control of borrowing and lending of time slots is decentralised among the nodes on the link.

Description

A METHOD FOR HANDLING RESOURCES IN A DIGITAL TIME DIVISION MULTIPLEXED COMMUNICATION NETWORK

TECHNICAL FIELD OF THE INVENTION

The present invention relates to a method m connection with controlling utilisation of communication resources m a digital time-division multiplexed communication network. More particularly, the present invention relates to allocation of time slots m a Dynamic synchronous Transfer Mode (DTM) network.

BACKGROUND

A DTM network is an example of a circuit switched time- division multiplexed communication network designed for broadband data transfer m public and local area networks. For a detailed description of the DTM architecture, see for example Chπster Bohm, Per mdgren, Lars Ramfelt, and Peter Sjodin, "The DTM Gigabit Network", Journal of High Speed Networks, 3(2), 109-126, 1994, and Lars Gauffin, Lars Hakansson, and B orn Pehrson, "Multi-gigabit networking based on DTM", Computer Networks and ISDN Systems, 24(2), 119-139, April 1992. The topology of a DTM network is based on unidirectional communication on time-division multiplexed bitstreams propagating on optical fibres, each bitstream preferably being accessed by multiple nodes, e.g. m a bus or ring structure. The bandwidth of each wavelength is divided into 125 μs frames, which m turn are divided into 64-bit time slots. Write access to such slots is governed by allocation of slots to different nodes. A node may v/πte data into a specific slot, i.e. into a specific time slot position withm each frame, only if the node has write access to this specific slot position. The slot access protocol guarantees the slot access to be conflict free, which means tha any two or more nodes do not write data IΓXO the same slot. In a system of this kind, write access to the time slots of said frame is typically distributed among the nodes having access to said bitstream. A node will thus typically own a number of time slots withm the frame and may thereby use these time slots for transmission. Also, slot ownership may be changed when required. For example, a node that owns a time slot may, if so requested or required, give away slot ownership of that time slot to a second node that is m need of capacity. The other node will thus be the new owner of the time slot and will, from then on, have the write access to this slot.

In an example of such a system, wherein the feature of time slot ownership is accompanied by a feature of slot borrowing, a first node that owns a time slot may also, if so desired or required, temporarily lend the write access to that time slot to a second node that for some reason requires more transmission capacity. In such a case, the second node borrowing the time slot will temporarily have the write access to the time slot, but will typically be obliged to, at some point time, return write access to the slot to the owner of the slot, i.e. to the first node. O9736402 discloses a method a communication network of the aforementioned kind, which the degree of temporary allocation of time slots is evaluated, and m which, responsive to the evaluation of temporary allocation, the number of slots being owned by nodes is changed accordingly. That is, the ownership of a time slot is transferred from one node to another based on the degree of borrowing of time slots.

In this and similar kinds of systems utilising transferable resources, the signalling preceding the reallocation of a time slot produces overhead signalling the network, thereby introducing a problem of reduced bandwidth available for data transfer. Moreover, attempts to reduce the overhead signalling due co time slot reallocat on can cause further problems relating to deteriorating fragmentation of time slots the network. It is preferred that reallocation of time slots between nodes is quick and "simple", i.e. not introducing excess control needs m the network, for providing adaptability to the instantaneous data transfer requirements of the nodes. However, means must be provided for preventing severe fragmentation of time slots m the long-term perspective . Thus, a general statement of a problem related to the prior art is how to facilitate long and short term allocation of time slots, while still allowing of efficient procedures of time slot reallocation without unnecessary signalling between the nodes There is thus a need for new methods for controlling allocation of time slots a time-division multiplexed communication network, which methods provide adaptability to instantaneous requirements of data transfer, while preventing long-term fragmentation m the network. SUMMARY OF THE INVENTION

It is an ob ect of the present invention to provide a solution to the above problems, and to eliminate other problems and difficulties the prior art, by means of a method as set forth claim 1 According to the present invention, the control of ownership change of time slots is thus centralised to one node operative to control distribution changes of time slot ownership on behalf of at least two or more other nodes on a link, while the procedure of borrowing/lending of time slots is decentralised the network, i.e. the responsibility of controlling loan of time slots is left to the nodes themselves, without interference from the node controlling the ownership

In one aspect of the present invention, loan and ownership of time slots is handled by separate mechanisms, thereby making implementation of these features less complicated. Furthermore, the requirements on the chosen implementation are relaxed by the mechanisms being separate. In another aspect of the present invention, a method is provided where the short term needs m the system, such as instantaneous demand for write access to time slots, is controlled by a decentralised loan procedure, while long term needs, such as ownership of time slots and avoidance of fragmentation, is controlled by a centralised procedure.

The present invention thus introduces the advantage of loan and ownership procedures being implemented at beneficial parts of the network. Accordingly, loan of time slots (short term needs) is controlled by distributed (decentralised) functions m the system and is thereby instantaneously responsive to changing demands of write access to time slots. Ownership of time slots and fragmentation issues (long term needs) is, on the other hand, controlled by centralised functions the system, thereby providing an overall view and long term structure of time slot ownership. The use of a centralised approach for control of slot ownership simplifies design without negatively affecting channel set-up delays, as changes slot ownership are typically performed on a long term basis.

BRIEF DESCRIPTION OF THE DRAWINGS

The objects and features of the present invention will be apparent from the following detailed description of a preferred embodiment when read conjunction with the drawings, m which:

Fig. la is a schematic view of an exemplary topology of a time -division multiplexed network,

Fig lb illustrates a preferred frame structure, and how the frames are divided into time slots, Fig. 2 is a schematic signalling diagram showing a loan procedure, and

Fig. 3 is a schematic signalling diagram showing an ownership change procedure . DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

An exemplary communication network N m accordance with the present invention is shown fig. la. In this case, the topology is a single-ring structure comprising one unidirectional ring link L. All nodes N on the link L can thus communicate by sending messages on the link.

The bandwidth of the link is divided into essentially fixed size, e.g. 125 μs, frames each comprising essentially fixed size, e.g. 64 bit, time slots, as shown fig. lb. At a bitrate of 2 Gbps , the number of time slots within each frame is around 3900. For illustrative purposes only a few time slots are shown within each frame m fig. lb. The start of each frame is identified by a so-called synchronisation slot S, and the end of each frame is provided with so-called guard band slots G included to accommodate for small jitters m the network frame frequency. The remaining slots of the frame are control and data slots used for transporting control signalling and payload data, respectively, between the nodes N on the link L. Write access to the control and data slots are distributed, and may at any time be redistributed as desired, among the nodes N connected to the link L.

In a preferred embodiment of the invention, write access to time slots, ownership of time slots, and borrowing of time slots the exemplified network is handled by control messages sent and received by nodes m the network. These control messages include, but are not limited to, Resource Announce (RES_ANN) messages, Ownership Change Request (CH__REQ) messages, Resource Transfer Request (TR_REQ) messages, Resource Transfer (RES_TR) messages and Ownership Change (OWN_CH) messages.

In this exemplifying embodiment, a Resource Announce (RES_ANN) message can be sent by any node, preferably broadcast to all nodes on the same link, and includes information on the amount of free resources (time slots) being owned by the sending node. This message is intermittently sent by all the nodes on the link to keep the other nodes updated on the demands of each node. If one node needs more time slots it can send a Resource Transfer Request (TR_REQ) message to one or more nodes, thereby requesting a loan of time slots. Such message will contain the amount of required resources (number of time slots) . If the node receiving the request has a surplus of slots, it can comply with the request, and send a Resource Transfer (RES_TR) message to the requesting node identifying the slots for which write access thereto is being transferred. In this way, the borrowing and lending of time slots is distributed m the network, and handled by the borrowing and lending nodes.

If any node frequently needs to borrow time slots from other nodes, it can send an Ownership Change Request (CH_REQ) message to a master node, for example being appointed as the node having the lowest link layer address on the link, handling the ownership of time slots in the network, thereby alerting the master of a desired ownership change. This message includes information on the amount of required resources (i.e. number of time slots required) . The master node may at any time, for example based upon Ownership Change Request messages from nodes, based upon auditing the Resource Announce messages, based upon network operator input, based upon an evaluation of the degree of borrowing and lending of slots, or based upon input from another application decide to change the ownership distribution between nodes m the network. A change ownership distribution of time slots is initiated by an Ownership Change (OWN_CH) message sent by the master node to all the nodes on the link. This message is preferably broadcast, and includes information on which time slots are owned by which nodes. In this way, each node is informed about the ownership of every time slot. If a time slot that was previously owned by a certain node is no longer owned, nor use, by this node, the time slot is immediately transferred to the new owner by the old owner sending a Resource Transfer (RES__TR) message to the new owner. If, on the other hand, the time slot is being used by the old owner when the Ownership Change (OWN_CH) message transferring the ownership is received, the old owner will continue to use the slot, now being a borrowed time slot. As soon as the time slot is free (i.e. no longer use) it is transferred to the proper owner (of which the using node is aware due to the Ownership Change (OWN__CH) message) by the borrowing node sending a Resource Transfer message (RES_TR) to the new owner of the time slot . In this exemplifying embodiment, each time slot is, by each node the network, considered to be in a certain state. As far as one node is concerned, a time slot can be one of several states including, but not being limited to, the following states: FREE, i.e. the time slot is available for immediate use by the node ;

BUSY, i.e. the time slot is used for transfer of data by the node, i.e. allocated to a channel (the time slot may be either owned by the node at issue or borrowed from another node) ^■

LENT, i.e. the time slot is owned by the node, but is temporarily allocated (lent) to another node; and

LOST, i.e. the time slot is neither owned by the node at issue, nor borrowed from another node. The state of a time slot will be affected in the following way, depending on its initial state, responsive to an Ownership Change message.

If the time slot is initially in the FREE state, and the time slot is still owned by the node at issue after receiving the Ownership Change (OWN_CH) message, the time slot remains in the FREE state. If the time slot, on the other hand, is owned by another node after receiving the Ownership Change (OWN_CH) message, the time slot will go into the LOST state, and a Resource Transfer (RES_TR) message will be sent to the new owner.

If the time slot is initially in the LENT state, and the time slot is still owned by the node at issue after receiving the Ownership Change (OWN__CH) message, the time slot remains in the LENT state. If the time slot, on the other hand, is owned by another node after the Ownership Change (OWN_CH) message, the time slot will go into the LOST state, without any further action.

If the time slot is initially in the LOST state, and the time slot is owned by the node at issue after receiving the Ownership Change (OWN_CH) message, the time slot will go into the LENT state. As soon as the node at issue receives a Resource Transfer (RES_TR) message regarding the particular time slot (from the previous owner) , the slot will go into the FREE state. If the time slot, on the other hand, is still owned by another node after reception of the Ownership Change (OWN_CH) message, the time slot will remain in the LOST state.

If the time slot is in the BUSY state when the Ownership Change (OWN_CH) message is received, the time slot will remain in this state regardless of the contents of the Ownership Change (0WN_CH) message. However, upon deallocation of the time slot from a channel, the time slot will go into the FREE state if the slot is still owned by the node at issue. If the slot is no longer owned by the node at issue after the Ownership Change (OWN_CH) message, the deallocation will put the slot in the LOST state, and a Resource Transfer (RES_TR) message will be sent to the new owner.

An ownership change procedure will now be described m more detail, with reference to figure 2. For illustrative purposes, a link is considered to comprise three nodes: A, B and C. In this example, node C is a master node handling the distribution of time slot ownership between the nodes. All the nodes on the link intermittently broadcast Resource Announce (RES_ANN) messages 10 to all nodes on the link, these messages containing information on the number of slots m the FREE state at the respective sender of the message, and optionally information about a safe margin buffer or the number of slots being borrowed from other nodes. It is now assumed that node B comes to the conclusion that is would be beneficial if it could own more slots. Node B then sends an Ownership Change Request message (CH_REQ) 11 to node C (the master node) , requesting ownership of a greater number of slots. It is not required by the master node to receive an Ownership Change Request for making a decision about ownership redistribution, but it is taken as an alert about a desire for redistribution of slot ownership. Based on an audit of the Resource Announce messages 10, and optionally on received Ownership Change Request messages 11, it is assumed that the master node C decides to change the ownership of time slots, where node B is to take over the ownership of certain slots from node A. Consequently, master node C broadcasts an Ownership Change message (OWN_CH) 12 containing the new ownership distribution to all nodes on the link. Responsive to the Ownership Change message 12, node B will conclude that a greater number of slots are now to be owned by node B, while node A will conclude that a smaller number of slots are now to be owned by node A.

All new slots allocated to node B will be put the LENT state by node B until write access to these slots is transferred to (and received by) node B. Any slots that are m the FREE state at node A, and for which node B is to be the new owner, are then more or less immediately transferred to node B (through a RES__TR message 13a) , thereby entering the LOST state at node A and entering the FREE state at node B. Slots used by (i.e. being m the BUSY state of) node A, and for which node B is to be the new owner, remains m the BUSY state at node A as long as the channel to which these slots are allocated is being used for transmission of data. As soon as the slots are deallocated from the channel, they are transferred to node B (the new owner) through another RES_TR message 13b, node A then putting the slot m the LOST state, and node B putting the slot the FREE state. In this way, an ownership change of time slots from node A to node B is ordered by the master node without the master node interfering with or having to consider the channels to which some of the slots are allocated.

With reference to fig. 3, a loan procedure will now be described further detail. For illustrative purposes, a link is considered to comprise three nodes: A, B and C.

As the previous example, node C is assumed to be a master node controlling the ownership of time slots.

However, the master node is not as such involved the loan procedure.

As illustrated, node A announces its resources by broadcasting a Resource Announce message (RES__ANN) 20 to all other nodes (including the master node) . In the exemplified situation, node B requires write access to a greater number of time slots for transmission of data. Bγ the Resource Announce (RES_ANN) message 20 sent by node A, node B receives the assumed information that node A keeps a surplus of time slots. To initiate the loan procedure, node B sends a Transfer Request (TR_REQ) message 21 to node A, requesting a transfer of time slots to node B (i.e. requesting a transfer of write access to time slots) . Node A replies to the request (complies with the request) by sending a Resource Transfer (RES_TR) message 22, containing an identification of the transferred time slots, to node B, node B thereby gaining write access to, i.e. borrowing, the identified time slots. Node B then starts to transmit data using the transferred time slots. When the data transmission is complete, node B returns some, or all, of the borrowed time slots to node A by sending a Resource Transfer (RES_TR) message 23 to node A, containing an identification of the returned time slots. In this example, the ownership of the borrowed time slots did not change during the loan procedure. However, if the time slots borrowed by node B have a new owner when they are to be returned, they are returned to the proper (new) owner. In this way, a versatile short term allocation (loan) of time slots is accomplished without causing long term fragmentation. Note that the master node C is completely outside the loan procedure. The master node C may, however, audit the loan procedure by listening to the messages sent by the borrowing and lending nodes. Moreover, the master node C itself may of course participate a loan procedure as any other node on the link, whereby the master not does not act as a master node, but rather as a normal borrowing/lending node, m accordance with the inventive loan procedure not requiring any controlling master node.

Consequently, loan of time slots between nodes is taking place the system without interference from the master node, and ownership change is controlled by the master node without essentially interfering with any ongoing loan between nodes or actual use of slots on the link.

The present invention thus provides a method that significantly improves the efficiency of resource use m the communication system To be noted, although time slot ownership and/or borrowing/lending has been described herein primarily with respect to time slot positions as such within a recurrent frame, such access could also advantageously be negotiated with respect to only a portion of the concerned link, thereby making it possible for different nodes to have access/control of the same time slot over different portions of the link, sometimes referred to as "slot reuse" . The above disclosure of a preferred embodiment is not intended to limit the scope of the invention, but should merely be taken as a preferred mode of carrying out the invention. The scope of the invention is defined in the appended claims .

Claims

1. A method for handling resources in a digital time- division multiplexed communication network, said network comprising nodes on a link, which nodes are capable of having ownership of time slots and capable of borrowing and lending time slots, comprising the steps of: controlling, centralised to one of said nodes on the link, changes of time slot ownership on behalf of at least two or more other nodes on the link, and controlling, decentralised among said nodes on the link, time slot borrowing and time slot lending.

2. A method according to claim 1, in which said step of controlling, decentralised among said nodes on the link, time slot borrowing and time slot lending is performed by a node that is to borrow a time slot and a node that is to lend the same time slot.

3. A method according to claim 1, in which said step of controlling, centralised to one of said nodes on the link, ownership of time slots is performed m a master node by said master node making a decision about a time slot ownership change, and sending a message imperative of a time slot ownership change, to said two or more other nodes on the link.

4. A method according to claim 1, which said step of controlling, centralised to one of said nodes on the link, changes of time slot ownership on behalf of at least two or more other nodes on the link is performed on behalf of all nodes on said link.

5. A method according to claim 4, in which changes of time slot ownership is signalled by an ownership change message, broadcast to all nodes on said link.

6. A method according to claim 2, in which said step of controlling, decentralised among said nodes on the link, time slot borrowing and time slot lending is performed by said node that is to borrow said time slot and said node that is to lend said time slot by signalling, regarding loan of said time slot, between the node that is to borrow said time slot and the node that is to lend said time slot.

7. A method according to claim 6, in which said loan is accomplished by exchanging a message, comprising a request for a transfer of write access to said time slot, sent by the node that is to borrow said time slot to the node that is to lend said time slot, and a message, imperative of a resource transfer, sent by the node that is to lend said time slot to the node that is to borrow said time slot.

8. A method according to any of the preceding claims, in which said time slots refer to time slot positions in a recurring frame on said link.

9. A method according to claim 8, in which the time slots are time slots on a shared link, thereby allowing a transfer of time slot resources between nodes connected to the same shared link.

10. A system for handling resources in a digital time- division multiplexed communication network, said network comprising nodes on a link, which nodes are capable of having ownership of time slots and capable of borrowing and lending time slots , c h a r a c t e r i s e d in that one of said nodes on the link is operative to control distribution changes of time slot ownership on behalf of at least two or more other nodes on the link, while control of borrowing and lending of time slots is decentralised among said nodes on the link.