Non-preemptive scheduling in network elements

Details Non-preemptive scheduling in network elements Non-preemptive scheduling in network elements

2005-10-17

2010-06-08

Abelson, Ronald (Department: 2476)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S235000, C370S237000, C370S238000, C370S231000

Reexamination Certificate

active

07733895

ABSTRACT:
A graph based on a data traffic matrix represents the occupancy of a set of virtual output queues to an optical crosspoint packet data switch. Edges in the graph are assigned to a matching in order of decreasing weight, provided that the edges do not conflict with other edges previously placed in the matching. If a conflict is found for a particular edge, a new matching is created and the conflicting edge is placed in the new matching. The process iterates until all edges are covered, resulting in creating a collection of matchings. The collection of matchings is transformed into a schedule such that each matching defines a switch configuration and the weight of the heaviest edge determines its holding time. The length of the obtained schedule equals the total cost of the collection. The cost of the collection is the total weight of the matchings plus the product of the re-configuration delay and the number of matchings.

REFERENCES:
patent: 2001/0026558 (2001-10-01), Kamiya
N. McKeown, “The iSLIP Scheduling Algorithm for Input-Queued Switches,” IEEE/ACM Transactions on Networking, vol. 7, No. 2, pp. 188-201, Apr. 1999.
Bertossi, Bongiovanni and Bonuccelli. Time Slot Assignment in SS/TDMA systems with intersatellite links.IEEE Trans. on Communication, 35:602-608. 1987.
C. C. Ribeiro et al., “An Optimal Column-Generation-with-Ranking Algorithm for Very Large Scale Set Partitioning Problems in Traffic Assignment,” European Journal of Operational Research, vol. 41, pp. 232-239, 1989.
Gopal and Wong. Minimizing the Number of Switchings in a SS/TDMA System.IEEE Trans. Communication,33:497-501, 1985.
Shlomi Dolev et al., “Bounded Latency Scheduling Scheme for ATM Cells,” Proceedings of the 4th IEEE Symposium on Computers and Communications (ISCC'99), pp. 273-277.
Ganz and Gao. Efficient Algorithms for SS/TDMA scheduling.IEEE Trans. on Communication,38:1367-1374. 1992.
Bonuccelli, Gopal and Wong. Incremental Time Slot Assignement in SS/TDMA satellite systems.IEEE Trans. on Communication,39:1147-1156. 1991.
Inukai. An Efcient SS/TDMA Time Slot Assignment Algorithm.IEEE Trans. on Communication,27:1449-1455, 1979.
V. Vokkarane et al., “Segmentation-Based Non-Preemptive Scheduling Algorithms for Optical Burst-Switched Networks,” University of Texas at Dallas, 2003, pp. 1-12.
F. Afrati et al., “Scheduling in switching networks with set-up delays,” Athens University of Economics & Business, Athens, Greece, pp. 1-6, 2003.
Li and Hamdi, λ-Adjust Algorithm for Optical Switches with Reconguration Delay.Proc. of ICC'03.
Crescenzi, Deng and Papadimitriou. On Approximating a Scheduling Problem,Journal of Combinatorial Optimization, 5:287-297, 2001.
Towles and Dally. Guaranteed Scheduling for Switches with Conguration Overhead.Proc. of INFOCOM'02.
A. Kesselman et al., “Non-Preemptive Scheduling of Optical Switches,” paper presented at IEEE Globecom Conference, Dallas, Nov. 30, 2004, pp. 1-6.
A. Kesselman et al., “Non-Preemptive Scheduling of Optical Switches,” slide presentation presented at IEEE Globecom Conference, Dallas, Nov. 30, 2004, pp. 1-25.
M. Prais et al., “Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment,” Informs Journal on Computing, vol. 12, pp. 164-176, 2000.

Affiliated with

Also associated with

Rating

Non-preemptive scheduling in network elements does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Non-preemptive scheduling in network elements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-preemptive scheduling in network elements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4208217