Defragmentation of communication channel allocations

• US 7,912,081 B2
• Filed: 03/23/2006
• Issued: 03/22/2011
• Est. Priority Date: 04/22/2005
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Olympus Corporation
• Inventors: Heidari-Bateni, Ghobad, Czaja, Stanislaw
• Primary Examiner(s): Addy; Anthony S.
• Application Number:
  US11/388,889
• Publication Number:
  US 20060264177A1
• Time in Patent Office: 1,825 Days
• Field of Search: 455/450, 455/452.1, 455/452.2, 455/453, 455/464, 455/509, 455/41.2, 455/62, 455/447, 455/450.451, 455/502, 455/512, 455515-517, 370/229, 370/232, 370/252, 370/253, 370/468, 370/310, 370/321, 370/322, 370328-330, 370336-338, 370/345, 370/347, 370/348, 370/376, 370/395.21, 370/431, 370/442, 370/443, 370/458, 370/459, 370/508, 709/223, 709/226, 709/229, 725/95, 725/96
• US Class Current: 370/443
• CPC Class Codes: H04N 21/238 Interfacing the downstream path of the transmission network, e.g. adapting the transmission rate of a video stream to network bandwidth; Processing of multiplex streams hybrid fiber coaxial [HFC] networks for downstream channel allocation for video distribution H04L12/2801; flow control in packet networks H04L47/10; real-time communication protocols in data switching networks H04L65/00; scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/64738 Monitoring network characteristics, e.g. bandwidth, congestion level data switched network analysis H04L41/14; monitoring functioning in data switched networks H04L43/0817; flow control in packet networks H04L47/10
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• CPC Class Codes: H04W 28/20 Negotiating bandwidth
• CPC Class Codes: H04W 72/00 Local resource management
• CPC Class Codes: H04W 72/0453 Resources in frequency domain, e.g. a carrier in FDMA
• CPC Class Codes: H04W 72/566 of the information or information source or recipient
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02

Abstract

Approaches scheduling and allocation of communication bandwidth across a communication channel provide the opportunity for improved network utilization. A network device is configured to allocating its bandwidth utilization within a communication network, wherein bandwidth allocation is governed by a utilization policy. The network device conducts communication activities within the communication network. When the network device deviates from the utilization policy in scheduling or conducting network activities, a penalty can be imposed on the network device for deviating from the utilization policy. Where one or more network conditions exceed predetermined tolerance levels, the offending network device can be required to reallocate its scheduled activities.

Claims

1. A method of medium access on a distributed communications network, wherein communication activities on the distributed communications network take place during communications windows, wherein a given communications window comprises a plurality of timeslots and a scheduling window that comprises a subset of the plurality of timeslots, the method comprising:

a network device transmitting a beacon to other network devices on the distributed communications network during a first scheduling window of a first communications window, wherein the beacon comprises a reservation of timeslots during a second communications window, and wherein the beacon further comprises an indication of whether the reservation of timeslots conforms with a predetermined timeslot reservation protocol shared among the network devices on the distributed communications network; and

the network device modifying its reservation of timeslots such that its reservation does not conflict with the other network device'"'"'s reservation when the beacon indicates that the reservation of timeslots does not conform with the predetermined timeslot reservation protocol and the network device receives a preemption request from another network device on the distributed communications network indicating that the network device'"'"'s reservation conflicts with the other network device'"'"'s reservation of timeslots during the second communications window;

wherein the plurality of timeslots of the given communications window are arranged into a plurality of groups of contiguous timeslots, each group of the plurality having an equal number of timeslots;

wherein the predetermined timeslot reservation protocol allows network devices to make horizontal reservations and vertical reservations, a horizontal reservation comprising a reservation of a timeslot at a specific slot location from each group of contiguous timeslots of the plurality of groups, and a vertical reservation comprising a reservation of a plurality of contiguous timeslots within a group of contiguous timeslots of the plurality of contiguous timeslots;

wherein the predetermined timeslot reservation protocol maintains a portion of the plurality of timeslots for horizontal reservations; and

wherein the reservation of timeslots that does not conform with the predetermined timeslot reservation protocol comprises a vertical reservation within the portion of the plurality of timeslots for horizontal reservations.

2. The method of claim 1, wherein the step of the network device modifying its reservation of timeslots comprises the network device conforming to the predetermined timeslot reservation protocol.

3. The method of claim 2, wherein the step of the network device modifying its reservation of timeslots takes place a predetermined number of communications windows after receiving the preemption request.

4. The method of claim 1, wherein the step of the network device modifying its reservation of timeslots takes place a predetermined number of communications windows after receiving the preemption request.

5. The method of claim 1, further comprising imposing a penalty on the network device for not conforming to the predetermined timeslot reservation protocol.

6. The method of claim 5, wherein the penalty imposed on the network device for deviating from the utilization policy comprises at least one of an extra monitoring task, extra reporting effort, and a limitation in bandwidth utilization.

7. The method of claim 5, wherein the penalty imposed on the network device is self-imposed.

8. The method of claim 5, wherein the penalty imposed is the refusal of a reward otherwise granted for conforming to a reallocation request.

9. The method of claim 5, wherein the penalty imposed is dynamically selected based on current network status.

10. The method of claim 5, wherein the penalty imposed is determined based on at least one of the magnitude of the deviation from the predetermined timeslot reservation, the frequency of deviation by the network device, the number of times the network device has deviated from the predetermined timeslot reservation, and the status of the distributed communications network.

11. A network device configured to operate within a distributed communication network, wherein communication activities on the distributed communications network take place during communications windows, wherein a given communications window comprises a plurality of timeslots and a scheduling window that comprises a subset of the plurality of timeslots, the network device comprising:

a housing;

at least one of a transmitter and receiver in the housing;

control logic, comprising hardware or computer executable program code embodied on a non-transitory storage medium, within the housing and configured to perform the steps of;

transmitting a beacon to other network devices on the distributed communications network during a first scheduling window of a first communications window, wherein the beacon comprises a reservation of timeslots during a second communications window, and wherein the beacon further comprises an indication of whether the reservation of timeslots conforms with a predetermined timeslot reservation protocol shared among the network devices on the distributed communications network; and

the network device modifying its reservation of timeslots such that its reservation does not conflict with the other network device'"'"'s reservation when the beacon indicates that the reservation of timeslots does not conform with the predetermined timeslot reservation protocol and the network device receives a preemption request from another network device on the distributed communications network indicating that the network device'"'"'s reservation conflicts with the other network device'"'"'s reservation of timeslots during the second communications window, modifying the network device'"'"'s own reservation of timeslots such that its reservation does not conflict with the other network device'"'"'s reservation;

wherein the plurality of timeslots of the given communications window are arranged into a plurality of groups of contiguous timeslots, each group of the plurality having an equal number of timeslots;

wherein the predetermined timeslot reservation protocol allows network devices to make horizontal reservations and vertical reservations, a horizontal reservation comprising a reservation of a timeslot at a specific slot location from each group of contiguous timeslots of the plurality of groups, and a vertical reservation comprising a reservation of a plurality of contiguous timeslots within a group of contiguous timeslots of the plurality of contiguous timeslots;

wherein the predetermined timeslot reservation protocol maintains a portion of the plurality of timeslots for horizontal reservations; and

wherein the reservation of timeslots that does not conform with the predetermined timeslot reservation protocol comprises a vertical reservation within the portion of the plurality of timeslots for horizontal reservations.

12. The network device of claim 11, wherein the step of the network device modifying its reservation of timeslots comprises the network device conforming to the predetermined timeslot reservation protocol.

13. The network device of claim 12, wherein the step of the network device modifying its reservation of timeslots takes place a predetermined number of communications windows after receiving the preemption request.

14. The network device of claim 11, wherein the step of the network device modifying its reservation of timeslots takes place a predetermined number of communications windows after receiving the preemption request.

15. The network device of claim 11, wherein the control logic is further configured such that a penalty is imposed on the network device for not conforming to the predetermined timeslot reservation protocol.

16. The network device of claim 15, wherein the penalty imposed on the network device for deviating from the predetermined timeslot reservation protocol comprises at least one of an extra monitoring task, extra reporting effort, and a limitation in bandwidth utilization.

17. The network device of claim 15, wherein the penalty imposed on the network device is self-imposed.

18. The network device of claim 15, wherein the penalty imposed is the refusal of a reward otherwise granted for conforming to a reallocation request.

19. The network device of claim 15, wherein the penalty imposed is dynamically selected based on current network status.

20. The network device of claim 15, wherein the penalty imposed is determined based on at least one of the magnitude of the deviation from the predetermined timeslot reservation protocol, the frequency of deviation by the network device, the number of times the network device has deviated from the predetermined timeslot reservation protocol, and the status of the distributed communication network.

21. A non-transitory storage medium having executable program code embodied thereon, the executable program code configured to cause a network device to perform a medium access method on a distributed communications network, wherein communication activities on the distributed communications network take place during communications windows, wherein a given communications window comprises a plurality of timeslots and a scheduling window that comprises a subset of the plurality of timeslots, the method comprising:

a network device transmitting a beacon to other network devices on the distributed communications network during a first scheduling window of a first communications window, wherein the beacon comprises a reservation of timeslots during a second communications window, and wherein the beacon further comprises an indication of whether the reservation of timeslots conforms with a predetermined timeslot reservation protocol shared among the network devices on the distributed communications network; and

the network device modifying its reservation of timeslots such that its reservation does not conflict with the other network device'"'"'s reservation when the beacon indicates that the reservation of timeslots does not conform with the predetermined timeslot reservation protocol and the network device receives a preemption request from another network device on the distributed communications network indicating that the network device'"'"'s reservation conflicts with the other network device'"'"'s reservation of timeslots during the second communications window;

wherein the plurality of timeslots of the given communications window are arranged into a plurality of groups of contiguous timeslots, each group of the plurality having an equal number of timeslots;

wherein the predetermined timeslot reservation protocol allows network devices to make horizontal reservations and vertical reservations, a horizontal reservation comprising a reservation of a timeslot at a specific slot location from each group of contiguous timeslots of the plurality of groups, and a vertical reservation comprising a reservation of a plurality of contiguous timeslots within a group of contiguous timeslots of the plurality of contiguous timeslots;

wherein the predetermined timeslot reservation protocol maintains a portion of the plurality of timeslots for horizontal reservations; and

wherein the reservation of timeslots that does not conform with the predetermined timeslot reservation protocol comprises a vertical reservation within the portion of the plurality of timeslots for horizontal reservations.

22. The non-transitory storage medium of claim 21, wherein the step of the network device modifying its reservation of timeslots comprises the network device conforming to the predetermined timeslot reservation protocol.

23. The non-transitory storage medium of claim 21, wherein the step of the network device modifying its reservation of timeslots takes place a predetermined number of communications windows after receiving the preemption request.

24. The non-transitory storage medium of claim 22, wherein the step of the network device modifying its reservation of timeslots takes place a predetermined number of communications windows after receiving the preemption request.

25. The non-transitory storage medium of claim 21, wherein the medium access method further comprises imposing a penalty on the network device for not conforming to the predetermined timeslot reservation protocol.

26. The non-transitory storage medium of claim 25, wherein medium access method further comprises modifying the scheduling of communication activities when the scheduled activities deviate from the predetermined timeslot reservation protocol and the network is operating outside of predetermined levels for a condition of the network.

27. The non-transitory storage medium of claim 25, wherein the penalty imposed on the network device for deviating from the predetermined timeslot reservation protocol comprises at least one of an extra monitoring task, extra reporting effort, reallocation of the network device'"'"'s scheduled allocations and a limitation in bandwidth utilization.

28. The non-transitory storage medium of claim 25, wherein the penalty imposed is the refusal of a reward otherwise granted for conforming to a reallocation request.

29. The non-transitory storage medium of claim 25, wherein the penalty imposed is dynamically selected based on current network status.

30. The non-transitory storage medium of claim 25, wherein the penalty imposed is determined based on at least one of the magnitude of the deviation from the predetermined timeslot reservation protocol, the frequency of deviation by the network device, the number of times the network device has deviated from the predetermined timeslot reservation protocol, and the status of the distributed communication network.