Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2004-09-30
2008-11-25
Orgad, Edan (Department: 2619)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S400000
Reexamination Certificate
active
07457296
ABSTRACT:
A method and apparatus for sorting packets by packet schedulers using a connected trie data structure is described. According to one embodiment of the invention, the packet scheduler receives a packet on a network and assigns the packet a time stamp value. The packet is inserted into a trie data structure that represents a scheduling horizon and includes a plurality of packets. The packet scheduler transmits the packet over the network based on its sorted order within the trie data structure.
REFERENCES:
patent: 7110411 (2006-09-01), Saidi et al.
patent: 7212531 (2007-05-01), Kopelman et al.
patent: 2002/0136230 (2002-09-01), Dell et al.
patent: 2003/0081554 (2003-05-01), Huang et al.
patent: 2004/0100950 (2004-05-01), Basu et al.
patent: 2004/0111402 (2004-06-01), Waters et al.
patent: 2005/0114298 (2005-05-01), Fan et al.
C.R. Bennett and H. Zhang, “WF2Q: Worst-case Fair Weighted Fair Queueing”, Infocom'96, Mar. 1996.
J.C.R. Bennett and H. Zhang, “Why WFQ Is Not Good Enough for Integrated Services Networks”, Proceedings of NOSSDAV'96, Apr. 1996.
A. Demers, S. Keshav and S. Shenker, “Analysis and Simulation of a Fair Queueing Algorithm”, Proc. ACM SIGCOMM '89, pp. 1-12; also in Journal of Internetworking Research and Experience, V1, N1, Sep. 1990, pp. 3-26.
P. Goyal, H.M. Vin, and H. Cheng, “Start-time Fair Queuing: A Scheduling Algorithm for Integrated Services Packet Switching Networks”, IEEE/ACM Transactions on Networking, vol. 5, No. 5, pp. 690-704, Oct. 1997.
A. K. Parekh and R. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks”—The Single Node Case, IEEE/ACM Transactions on Networking, vol. 1, No. 3, pp. 344-357, Jun. 1993.
H. Zhang and E. Knightly, “Comparison of Rate-Controlled Static Priority and Stop-and-Go”, ACM/Springer Multimedia Systems: Special Issue on Multimedia Networking, (4)6:346-356, Dec. 1996
H. Zhang and D. Ferrari, “Rate-Controlled Static-Priority Queueing”, Proceedings of INFOCOM'93, San Francisco, CA, Apr. 1993 IEEE.
H. Zhang and S. Keshav, “Comparison of Rate-based Service Disciplines”, Proceedings of ACM SIGCOMM'91, Zurich, Switzerland, Sep. 1991.
Jon C.R. Bennett and H. Zhang, “Hierarchical Packet Fair Queueing Algorithms”,IEEE/ACM Transactions on Networking, 5(5):675-689, Oct. 1997. Also in Proceedings of SIGCOMM'96, Aug. 1996.
I. Stoica, H. Zhang and T. S. Eugene Ng, “A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Service”, Proceedings of SIGCOMM'97.
Hyman, J.M., Lazar, A.A. and Pacifici, G., “Real-Time Scheduling with Quality of Service Constraints”, IEEE Journal on Selected Areas in Communications, vol. SAC-9, No. 7, Sep. 1991, pp. 1052-1063.
Hyman, J.M., Lazar, A.A. and Pacifici, G., “A Separation Principle between Scheduling and Admission Control for Broadband Switching”, IEEE Journal on Selected Areas in Communications, vol. 11, No. 4, May 1993, pp. 605-616.
D. Eckhardt, P. Steenkiste. “Effort-limited Fair (ELF) Scheduling for Wireless Networks”, Proceedings of IEEE INFOCOM 2000, Tel Aviv, Israel.
S. Lu, V. Bharghavan and R. Srikant, “Fair Scheduling in Wireless Packet Networks”, IEEE/ACM Transcations on Networking, vol. 7, No. 4, Aug. 1999, pp. 473-489.
David D. Clark, Scott Shenker, Lixia Zhang, “Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism”, SIGCOMM 1992.
P. Goyal, S.S. Lam, and H.M. Vin, “Determining End-to-End Delay Bounds in Heterogeneous Networks”, Multimedia Systems (1997) 5: 157-163.
J. Kaur and H. Vin, “Core-stateless Guaranteed Throughput Networks”, in Proceedings of IEEE INFOCOM, San Francisco, CA, Apr. 2003.
Ion Stoica, Scott Shenker, Hui Zhang, “Core-Stateless Fair Queueing: A Scalable Architecture to Approximate Fair Bandwidth Allocations in High Speed Networks”, SIGCOMM'98.
Jon C.R. Bennett, Donpaul C. Stephens, Hui Zhang, “High Speed, Scalable, and Accurate Implementation of Packet Fair Queueing Algorithms in ATM Networks”. ICNP'97.
H. J. Chao, Y. R. Jenq, X. Guo, and C. H. Lam, “Design of Packet Fair Queuing Schedulers Using a RAM-based Searching Engine”, in IEEE J. Select. Areas Communications vol. 17, No. 6, pp. 1105-1126, 1999.
H. J. Chao, H. Cheng, Y. R. Jenq, and D. Jeong, “Design of a Generalized Priority Queue Manager for ATM Switches”, IEEE J. Select. Areas Communications vol. 15, No. 5, pp. 867-880, Jun. 1997.
J. Liebeherr and D. E. Wrege, “Priority Queue Schedulers with Approximate Sorting in Output Buffered Switches”, Proceedings of IEEE Infocom ' 97 [39], pp. 1-32.
Sung-Whan Moon, Jennifer Rexford, and Kang Shin, “Scalable Hardware Priority Queue Architectures for High-Speed Packet Switches,” IEEE Trans. on Computers, vol. XX, No. Y, Month 2000, pp. 1-16.
Sung-Whan Moon, “Implementing Traffic Shaping and Link Scheduling on a High-Performance Server”, 2001 IEEE, pp. 216-225.
Jennifer Rexford, Flavio Bonomi, Albert Greenberg, and Albert Wong, “Scalable Architectures for Integrated Traffic Shaping and Link Scheduling in High-Speed ATM Switches”, IEEE Journal on Selected Areas in Communications, vol. 15, No. 5, Jun. 1997, pp. 938-950. An earlier version appeared in Proc. IEEE INFOCOM, Apr. 1997, pp. 1056-1064.
Jennifer Rexford, John Hall, and Kang G. Shin, “A Router Architecture for Real-Time Communication in Multicomputer Networks,”IEEE Transactions on Computers, vol. 47, No. 10, Oct. 1998, pp. 1088-1101. An earlier version appeared in Proc. International Symposium on Computer Architecture, May 1996, pp. 237-246.
Jennifer Rexford, Albert Greenberg, and Flavio Bonomi, “Hardware-Efficient Fair Queueing Architectures for High-Speed Networks,” Proc. IEEE INFOCOM, Mar. 1996, pp. 638-646.
S. Keshav, “An Engineering Approach to Computer Networking”, Chapter 9, Addison Wesley, 1997, pp. 209-222.
P. van Emde Boas, R. Kaas and E. Zijlstra, “An O (nloglogn) On-Line Algorithm for the Insert-Extract Min Problem” , Dec. 1974, pp. 1-27.
Kounavis Michael
Kumar Alok
Yavatkar Raj
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Orgad Edan
Park Jung
LandOfFree
Method and apparatus for sorting packets in packet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for sorting packets in packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for sorting packets in packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4045285