Prevention of deadlocks and livelocks in lossless,...

Details Prevention of deadlocks and livelocks in lossless,... Prevention of deadlocks and livelocks in lossless,...

2005-02-22

2005-02-22

Nguyen, Brian (Department: 2661)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S235000, C370S412000, C370S429000

Reexamination Certificate

active

06859435

ABSTRACT:
A packet communication network is arranged so that a backpressure or feedback signal is sent from a receiving node to a node having packets to send to the receiving,node, selectively allowing only certain packets to be considered eligible for transmission. The backpressure is arranged to be lossless, and to avoid network deadlocks and livelocks. The transmission of a packet p from a sending node Xlto a receiving node Rl, via a link l, is controlled by (a) sending from the receiving node Rlto the upstream node Xla feedback value flthat assures that there will be room in the buffer in the receiving node Rlto store packets subsequently received from the upstream node Xl; (b) assigning a priority level λpto packets stored in the buffer of the receiving node Rl; and (c) transmitting from the sending node Xlto the receiving node Rl, only those stored packets at Xlwhose priority level λpexceeds the feedback value flreceived from the receiving node Rl.

REFERENCES:
patent: 4933933 (1990-06-01), Dally et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5369745 (1994-11-01), Faber
patent: 5471623 (1995-11-01), Napolitano, Jr.
patent: 5570348 (1996-10-01), Holden
patent: 5689508 (1997-11-01), Lyles
patent: 5724351 (1998-03-01), Chao et al.
patent: 5787071 (1998-07-01), Basso et al.
patent: 5790522 (1998-08-01), Fichou et al.
patent: 5838922 (1998-11-01), Galand et al.
patent: 6084855 (2000-07-01), Soirinsuo et al.
patent: 6122251 (2000-09-01), Shinohara
patent: 6240075 (2001-05-01), Takahashi et al.
patent: 6252849 (2001-06-01), Rom et al.
patent: 6259698 (2001-07-01), Shin et al.
patent: 6388993 (2002-05-01), Shin et al.
Coffman, E. G. et al., “System Deadlocks”, Computing Surveys, vol. 3, pp. 67-78, Jun. 1971.
Holt, R. C., “Some Deadlock Properties of Computer Systems”, Computing Surveys, vol. 4, pp. 179-196, 9/72.
Merlin, P. M. et al, “Deadlock Avoidance in Store-and-Forward Networks-I: Store-and-Forward Deadlock”, IEEE Trans. Commun., vol. COM-28, pp. 345-354, Mar. 1980.
Gunther, K. D. “Prevention of Deadlocks in Packet-Switched Data Transport Systems”, IEEE Trans. Commun., vol. COM-29, pp. 512-524, Apr. 1981.
Gopal, I. S., “Prevention of Store-and-Forward Deadlock in Computer Networks”, IEEE Trans. Commun., vol. COM-33, pp. 1258-1264, Dec. 1985.
Holzmann, G. J., Design and Validation of Computer Protocols, Englewood Cliffs, NJ; Prentice Hall, 1991.
Noureddine, W et al, “Selective Back-Pressure in Switched Ethernet LANs”, IEEE Globecom'99 Symposium on High Speed Networks, Dec. 1999, 1256-1263.
Kamolphiwong, S. et al., “Flow Control in ATM networks: a survey”, Comp. Commun., vol. 21, pp. 951-968, 1998).
Caruso, J. “Gigabit Ethernet ventures into the land beyond the Lan”, Network World, p. 36, May 1999.
Margalit, N. “Intelligent DWDM takes Gigabit Ethernet to the MAN”, Lightwave, p. 101, Jun. 1999.
Schroeder, M. D. et al., “Aautonet: A High-Speed, Self Configuring Local Area Network Using Point-to-Point Links”, IEEE J. Selected Areas Commun., vol. 9, pp. 1318-1335, Oct. 1991.
Dally, W. J. et al., “Deadlock-Free Message Routing in Multiprocessor Interconnection Networks”, vol. C-36, pp. 547-553, May 1987.
Leonardi, E. et al., “Congestion Control in Asynchronous, High Speed Wormhole Routing Networks”, IEEE Commun. Mag., pp. 58-69, Nov. 1996.
Iliadis, I., “A New Feedback Congestion Control Policy for Long Propagation Delays”, IEEE J. Select. Areas Commun., vol. 13, pp. 1284-1295, Sep. 1995.
Golestani, S. J. et al., “A Class of End-to-End Congestion Control Algorithms for the Internet”, Proc. 6thIntnl. Conf. On Network Protocols, Oct. 1998.
Karol, M. et al., A Simple Technique that Prevents Packet Loss and Deadlocks in Gigabit Ethernet, Proc. 1999 Intnl Symposium on Communications (ISCOM'99), pp. 26-30, Nov. 1999.

Affiliated with

Also associated with

Rating

Prevention of deadlocks and livelocks in lossless,... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Prevention of deadlocks and livelocks in lossless,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prevention of deadlocks and livelocks in lossless,... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3475350