Methods and apparatus for allocating time slots and fragments on communications lines between adjacent nodes in a high granularity switching system

Claim 2

In a digital data communication system comprising a plurality of nodes interconnected by communication lines, each communication line having a bandwidth, the bandwidth being divided into "m" slots, each one of the plurality of nodes being for transporting data from any of the m slots of any of the communication lines connected thereto to any other of the m slots of any of the communication lines connected thereto, allocation control apparatus in each one of the plurality of nodes for controlling allocation of data bandwidth to one or more of the m slots of line bandwidth associated with each communication line connected to a given node, comprising: a bit map means consisting of "m" bit locations, each bit location corresponding to a different slot on a given communication line between adjacent nodes, wherein each of said m bit locations is used for storing a binary bit which takes a value of ZERO for indicating that its corresponding slot is available or a value of ONE for indicating that its corresponding slot is in use and unavailable; allocation means for identifying an available slot on said given communication line by locating a corresponding ZERO in the bit map means, assigning data bandwidth to the available slot, and marking the slot as being in use by recording a ONE in the slot's corresponding bit location in said bit map means; and deallocation means for deassigning data bandwidth from a slot, off said given communication line, and for marking the slot as available by recording a ZERO in the corresponding bit location in said bit map means.

Claim 3

The digital data communication system recited in claim 1 wherein each of said communication lines interconnects a first node and a second node adjacent to said first node, and includes a signalling channel for exchanging procedural information between the first node and the second node, and further wherein the allocation control apparatus within each of the plurality of nodes is further adapted such that: the bit map means is linearly organized, having a first end and a second end opposite to the first end; and in the allocation means available slots are identified by the first node beginning from the first end of the bit map means, and by the second node beginning with the second end of the bit map means.

Claim 4

The digital data communication system recited in claim 2 wherein each of the two adjacent nodes further includes means for informing the other, via the signalling channel, of slot allocations it has made, and each of the two adjacent nodes further includes means for updating the bit map means for each communication line interconnecting the two adjacent nodes according to information thus received via the signalling channel.

Claim 5

In a digital data communication system comprising a plurality of nodes interconnected by communication lines, each communication line having a bandwidth, the bandwidth being divided into "m" slots, the slots each being subdivided into "n" fragments, each one of the plurality of nodes being for transporting data from any of the m×n fragments of any of the communication lines connected thereto to any other of the m×n fragments of any of the communication lines connected thereto, allocation control apparatus in each one of the plurality of nodes for controlling allocation of data bandwidth to one or more of the m×n fragments of line bandwidth associated with each communication line connected to a given node, comprising: a bit map means consisting of m×n bit locations, each bit location corresponding to a different fragment on a given communication line between adjacent nodes, wherein each one of said m×n bit locations is used for storing a binary bit which takes a value of ZERO for indicating that its corresponding fragment is available or a value of ONE for indicating that its corresponding fragment is in use and unavailable; allocation means for identifying an available fragment on a given communication line by locating a corresponding ZERO in the bit map means, assigning data bandwidth to the available fragment, and marking the fragment as being in use by recording a ONE in the fragments corresponding bit location in said bit map means; and deallocation means for deassigning data bandwidth from a fragment, off said given communication line, and for marking the fragment as available by recording a ZERO in the corresponding bit location in said bit map means.

Claim 6

In a digital data communication system comprising a plurality of nodes interconnected by communication lines, each communication line having a bandwidth, the bandwidth being divided into "m" slots, the slots each being subdivided into "n" fragments, each one of the plurality of nodes being for transporting data from any of the m×n fragments of any of the communication lines connected thereto to any other of the m×n fragments of any of the communication lines connected thereto, allocation control apparatus in each one of the plurality of nodes for controlling allocation of data bandwidth to one or more of the m×n fragments of line bandwidth associated with each communication line connected to a given node, comprising: a bit map means consisting of m×n bit locations, each bit location corresponding to a different fragment on a given communication line between adjacent nodes, wherein each one of said m×n bit locations is used for storing a binary bit which takes a value of ZERO for indicating that its corresponding fragment is available or a value of ONE for indicating that its corresponding fragment is in use and unavailable; allocation means for identifying an available fragment on a given communication line by locating a corresponding ZERO in the bit map means, assigning data bandwidth to the available fragment, and marking the fragment as being in use by recording a ONE in the fragments corresponding bit location in said bit map means; and deallocation means for deassigning data bandwidth from a fragment, off said given communication line, and for marking the fragment as available by recording a ZERO in the corresponding bit location in said bit map means.

Claim 7

The digital data communication system recited in claim 4 wherein each of said communication lines interconnects a first node and a second node adjacent to said first node, and includes a signalling channel for exchanging procedural information between the first node and the second node, and further wherein the allocation control apparatus within each of the plurality of nodes is further adapted such that: the bit map means is linearly organized, having a first end and a second end opposite to the first end; and in the allocation means available fragments are identified by the first node beginning from the first end of the bit map means, and by the second node beginning with the second end of the bit map means.

Claim 8

The digital data communication system recited in claim 5 wherein each of the adjacent two nodes further includes means for informing the other, via the signalling channel, of fragment allocations it has made, and each of the two adjacent nodes further includes means for updating the bit map means for each communication line interconnecting the two adjacent nodes according to information thus received via the signalling channel.

Claim 11

A method as set forth in claim 7 further comprising the step of deallocating previously allocated bandwidth on a selected line connected to a given node by changing the state of the bit corresponding to the time slot being dellocated.

Claim 12

A method as set forth in claim 8 wherein each bit map is linearly organized, having a first end and a second end opposite to said first end, and further wherein the step of allocating bandwidth on a selected line, connected to said given node and an adjacent node, is performed by identifying an available time slot starting at the first end of the bit map maintained at said given node for said selected line.

Claim 13

A method as set forth in claim 9 wherein said step of allocating bandwidth on said selected line is further performed by identifying an available slot starting at the second end of the bit map maintained at the adjacent node for said selected line.

Claim 16

A method as set forth in claim 11 further comprising the step of deallocating previously allocated bandwidth on a selected line connected to a given node by changing the state of the bit corresponding to the fragment being deallocated.

Claim 17

A method as set forth in claim 12 wherein each bit map is linearly organized, having a first end and a second end opposite to said first end, and further wherein the step of allocating bandwidth on a selected line connected to said given node and an adjacent node is performed by identifying an available fragment starting at the first end of the bit map maintained at said given node for said selected line.

Claim 18

A method as set forth in claim 13 wherein said step of allocating bandwidth on said selected line is further performed by identifying an available fragment starting at the second end of the bit map maintained at the adjacent node for said selected line.

Claim 19

The digital communications system as set forth in claim 3 further comprising means for allocating time slots on a non-contiguous basis.

Claim 20

The digital communications system as set forth in claim 6 further comprising means for allocating fragments on a non-contiguous basis.

Claim 21

A method as set forth in claim 7 wherein said step of allocating bandwidth may be performed utilizing noncontiguous time slots.

Claim 22

A method as set forth in claim 11 wherein said step of allocating bandwidth may be performed utilizing noncontiguous fragments.

Claim 23

A digital communication system as set forth in claim 3 wherein the number of slots per line, m, is chosen such that the system exhibits at least an 8 kbps switching granularity.

Claim 24

A digital communications system as set forth in claim 6 wherein the number of fragments per line, m×n, is chosen such that the system exhibits at least an 8 kbps switching granularity.