Calendar heap system and method for efficient sorting

Details Calendar heap system and method for efficient sorting Calendar heap system and method for efficient sorting

2007-06-26

2007-06-26

Ferris, Derrick W. (Department: 2616)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

Reexamination Certificate

active

10281033

ABSTRACT:
A calendar heap structure and method for sorting N timestamp (TS) values in an ATM fabric scheduler implemented in an access network element. The heap structure is implemented using a radix value (R) for grouping the N TS values into a number of groups. Validity bits associated with the TS values are hierarchically arranged in a tree having logR(N) levels, wherein the bottom layer's N bits correspond to pointers that point to linked lists of flows with respective TS values. Starting from the top level heap, each subsequent level's heaps are successively examined for determining which particular heap obtains a minimum value until a particular validity bit of the bottom level is reached, which validity bit points to the minimum TS.

REFERENCES:
patent: 4878048 (1989-10-01), Gottesman et al.
patent: 5119370 (1992-06-01), Terry
patent: 5237565 (1993-08-01), Henrion et al.
patent: 5287355 (1994-02-01), Takahashi et al.
patent: 5383180 (1995-01-01), Kartalopoulos
patent: 5396622 (1995-03-01), Lee et al.
patent: 5526344 (1996-06-01), Langdon et al.
patent: 5734656 (1998-03-01), Prince et al.
patent: 5784371 (1998-07-01), Iwai
patent: 5850399 (1998-12-01), Ganmukhi et al.
patent: 5859835 (1999-01-01), Varma et al.
patent: 5862136 (1999-01-01), Irwin
patent: 5875190 (1999-02-01), Law
patent: 5878042 (1999-03-01), Fraas et al.
patent: 5889773 (1999-03-01), Stevenson, III
patent: 5896382 (1999-04-01), Davis et al.
patent: 5901024 (1999-05-01), Deschaine et al.
patent: 5926479 (1999-07-01), Baran
patent: 5953338 (1999-09-01), Ma
patent: 6064650 (2000-05-01), Kappler et al.
patent: 6064651 (2000-05-01), Rogers et al.
patent: 6081507 (2000-06-01), Chao et al.
patent: 6128295 (2000-10-01), Larsson et al.
patent: 6353593 (2002-03-01), Chen
patent: 6370159 (2002-04-01), Eidson
patent: 6389031 (2002-05-01), Chao et al.
patent: 6396843 (2002-05-01), Chiussi et al.
patent: 6411957 (2002-06-01), Dijkstra
patent: 6415325 (2002-07-01), Morrien
patent: 6434140 (2002-08-01), Barany et al.
patent: 6480487 (2002-11-01), Wegleitner et al.
patent: 6480511 (2002-11-01), Petty
patent: 6574217 (2003-06-01), Lewis et al.
patent: 6728239 (2004-04-01), Kung et al.
patent: 6904060 (2005-06-01), Nelson et al.
patent: 6914898 (2005-07-01), Sasagawa et al.
patent: 6950441 (2005-09-01), Kaczmarczyk et al.
patent: 0 901 302 (1999-03-01), None
patent: 0 961 512 (1999-12-01), None
patent: 1 093 266 (2001-04-01), None
patent: 1 111 855 (2001-06-01), None
patent: 1 111 858 (2001-06-01), None
patent: 0 522 773 (2004-05-01), None
patent: 0 713 347 (2004-05-01), None
patent: 97/04558 (1997-02-01), None
patent: 00/11880 (2000-03-01), None
patent: 01/86884 (2001-11-01), None
Giroux, Natalie and Ganti, Sudhakar, “Queuing and Scheduling”, Quality of Service in ATM Networks: State of the Art Traffic Management, Chapter 5, pates 85-121.
Kaufman, Jill et al “ATM Forum Education Corner”, at http://www.atmforum.com/pages/library/53bytes/backissues/others/53bytes-0994-4.html.
Traffic Management Specification, The ATM Forum Technical Committee, Version 4.1, AF-TM-0121.000, Mar. 1999.
Knuth, D.E., “The Art of Computer Programming, vol. 3: Sorting and Searching”, 1973, Addison-Wesley Publishing Company, Inc. U.S.A. XP002271706.
Knuth, D.E.; “The Art of Computer Programming, vol. 3: Sorting and Searching”; 1973; Addison-Wesley Publishing Company, Inc.; USA.

Affiliated with

Also associated with

Rating

Calendar heap system and method for efficient sorting does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Calendar heap system and method for efficient sorting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Calendar heap system and method for efficient sorting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3829626