Nel lavoro presentato sono state sottolineate le potenzialit` a del network cal- culus per la schematizzazione e l’analisi prestazionale dei dispositivi di rete.

Conclusioni

Nel lavoro presentato sono state sottolineate le potenzialit` a del network cal- culus per la schematizzazione e l’analisi prestazionale dei dispositivi di rete.

Particolare attenzione ` e stata dedicata all’interpretazione pi` u squisitamente pratica di concetti ampiamente sviluppati da un punto di vista teorico in studi scientifici recenti, primo fra tutti il concetto di curva di servizio.

In tale contesto, sono emerse da una parte l’esigenza di avere a disposizio- ne modelli che garantiscano una validit` a generale e siano quindi il pi` u pos- sibile indipendenti dalle implementazioni specifiche, dall’altra la necessit` a che gli stessi modelli trovino riscontro nei casi reali con effetti praticamente misurabili.

Inoltre alla luce dell’analisi deterministica, fatta per worst case, ` e es- senziale che i modelli siano estremamente accurati onde evitare di ottenere bound oltremisura conservativi che possono tradursi, in fase di progetta- zione, in una sovrallocazione delle risorse. In effetti il compromesso tra la complessit` a e l’efficienza dei modelli di rete ` e di fatto un’area di ricerca ancora aperta [52].

In un’ottica orientata alla gestione della QoS in Internet il network cal-

culus risulta uno strumento molto attraente soprattutto perch´ e, pur facendo

136 Conclusioni

uso di concetti matematici relativamente semplici, consente di determinare bound estremamente utili per il dimensionamento degli elementi di rete.

Nell’ambito del presente lavoro di tesi, prendendo spunto dalle interes- santi implicazioni teoriche riscontrate in letteratura, ` e stata condotta una campagna di simulazioni atta a verificare la validit` a nonch´ e la bont` a di al- cuni bound. Ci` o ` e stato possibile dopo aver evidenziato come il modello LR, che permette di schematizzare adeguatamente la stragrande maggioranza degli algoritmi di scheduling, possa essere in ultima analisi ricondotto ad una curva di servizio del tipo latency rate.

L’analisi ` e stata condotta prendendo in considerazione l’algoritmo DRR che costituisce un buon compromesso tra fairness e complessit` a. Dal mo- mento che esso appartiene alla classe LR, pu` o essere caratterizzato da un elemento curva di servizio del tipo latency rate e ci` o permette di stabilire utili relazioni analitiche tra i flussi in ingresso e in uscita dallo scheduler.

Le simulazioni hanno dimostrato che la propriet` a di curva di servizio ri- sulta effettivamente soddisfatta e hanno permesso inoltre di fare interessanti osservazioni sull’interazione dei flussi nello scheduler.

In ultima istanza sono state verificate anche le propriet` a di concatenazio-

ne della curva di servizio, un aspetto della teoria di notevole rilevanza pratica

perch´ e consente di estendere l’ananlisi a topologie di rete pi` u complesse.

Bibliografia

[1] R. Braden, D. Clark, and S. Shenker. Integrated Services in the Internet Architecture: an Overview. RFC 1633, jun 1994.

[2] S. Blake et al. An Architecture for Differentiated Services. RFC 2475, Dec 1998.

[3] F. Baccelli, G. Cohen, G. J. Olsder, and J. P. Quadrat. Synchronization and Linearity, An Algebra for Discrete Event System. 1992.

[4] D. Stiliadis. Traffic Scheduling in Packet-Switched Networks: Analysis, Design and Implementation. PhD thesis, University of California, Santa Cruz, jun 1996.

[5] J.Y. Le Boudec and P. Thiran. Network Calculus-A Theory of Determi- nistic Queuing Systems for the Internet, volume LCNS 2050. Springer, Lecture Notes in Computer Science, 2001.

[6] A.K. Parekh and R.G. Gallager. A generalized processor sharing ap- proach to flow control in integrated services networks: The single node case. IEEE/ACM Transactions on Networking, 1, jun 1993.

[7] A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of fair

queuing algorithm. In Proc. Sigcomm ’89, sept 1989.

138 BIBLIOGRAFIA

[8] S. Golestani. A self-clocked fair queueing scheme for broadband applications. In Proceedings of IEEE INFOCOM ’94, apr 1994.

[9] J. C. R. Bennett and H. Zhang. Wf

q: Worst-case fair weighted fair queueing. In Proc. IEEE INFOCOM, mar 1996.

[10] M. Shreedhar and G. Varghese. Efficient fair queuing usin deficit round robin. In Proc. Siggcomm ’95, 1995.

[11] S. S. Kanhere and H. Sethu. On the latency bound of deficit round robin. In Proceedings of the International Conference on Computer Communications and Network, Miami, Florida, USA, oct 2002.

[12] R.L. Cruz. A calculus for network delay, part i: Network elements in isolation. IEEE Transactions on Information Theory, 37, jan 1991.

[13] R.L. Cruz. A calculus for network delay, part ii: Network analysis.

IEEE Transactions on Information Theory, 37, jan 1991.

[14] R. Agrawal, R.L. Cruz, C. Okino, and R. Rajan. Performance bounds for flow control protocols. IEEE/ACM Transactions on Networking, 3, jun 1999.

[15] C.S. Chang. On deterministic traffic regulation and service guarantee:

A systemetic approach by filtering. IEEE Transactions on Information Theory, 44, aug 1998.

[16] J.Y. Le Boudec. Application of network calculus to guaranteed service networks. IEEE Transactions on Information Theory, 44, may 1998.

[17] S. Shenker, C. Partridge, and R. Guerin. Specification of Guaranteed

Quality of Service. RFC 2212, Sept 1997.

BIBLIOGRAFIA 139

[18] J.Y. Le Boudec. Some properties of variable length packet shapers.

IEEE/ACM Transactions on Networking, 10, jun 2002.

[19] A. S. Tanenbaum. Reti di calcolatori. Pearson Education Italia, Milano, fourth edition, 2003.

[20] R.L. Cruz. Quality of service guarantees in virtual circuit switched networks. IEEE Journal on Selected Areas in Communications, 13, aug 1995.

[21] S. Chakraborty, S. K¨ unzli, and L. Thiele. A general framework for ana- lysing system properties in platform based embedded system designs.

IEEE, 2003.

[22] D. Stiliadis and A.Varma. Latency-rate servers: A general model for ananlysis of traffic scheduling algorithms. IEEE/ACM Transactions on Networking, 6, oct 1998.

[23] A.K. Parekh and R.G. Gallager. A generalized processor sharing ap- proach to flow control in integrated services networks: The multiple node case. IEEE/ACM Transactions on Networking, 2, apr 1994.

[24] J.Y. Le Boudec and A. Charny. Packet scale rate guarantee for non-fifo nodes. IEEE/ACM Transactions on Networking, 2003. Accepted for publication.

[25] R. Agrawal, R.L. Cruz, C. Okino, and R. Rajan. A framework for adaptive service guarantees. Proc. Allerton Conf. on Comm., Control, and Comp., Monticello, sep 1998.

[26] J.C.R. Bennett, K. Benson, A. Charny, W.F. Courtney, and J.Y. Le

Boudec. Delay jitter bounds and packet scale rate guarantee for ex-

140 BIBLIOGRAFIA

pedited forwarding. IEEE/ACM Transactions on Networking, aug 2002.

[27] V. Jacobson and K.Nichols K. Poduri. Supplemental Information for the New Definition of the EF PHB (Expedited Forwarding Per-Hop Behavior). RFC 2598, June 1999.

[28] J.C.R. Bennett, K. Benson, A. Charny, F. Baker, W.F. Courtney, J.Y. Le Boudec, B. Davie, A. Chiu, S. Davari, V. Firoiu, C. Kalmanek, K. Ramakrisham, and D. Stiliadis. An Expedited Forwarding PHB (Per Hop Behavior). RFC 3246, March 2002.

[29] J.C.R. Bennett, K. Benson, A. Charny, F. Baker, W.F. Courtney, J.Y. Le Boudec, A. Chiu, S. Davari, V. Firoiu, C. Kalmanek, K. K.

Ramakrisham, and D. Stiliadis. Supplemental Information for the New Definition of the EF PHB (Expedited Forwarding Per-Hop Behavior).

RFC 3247, March 2002.

[30] D. Astuti. Packet handling. Technical report, Department of Computer Science, University of Helsinki, 2003.

[31] J. Nagle. On packet switches with infinite storage. IEEE Transactions on Communications, apr 1987.

[32] Y. Zhou and H. Sethu. On the relationship between absolute and re- lative fairness bounds. IEEE/ACM Communications Letters, 6, jan 2002.

[33] H. Shi and H. Sethu. An eavaluation of timestamp-based packet sche-

dulers using a novel measure of istantaneous fairness. In Proceedings of

IEEE Performance, Computing and Communications, apr 2003.

BIBLIOGRAFIA 141

[34] F. A. Cowell. Measuring inequality: techniques for social sciences. John Wiley & Sons, New York, 1977.

[35] L.L. Peterson and B.S. Davie. Computer Networks: A Systems Ap- proach. Morgan Kaufmann Publishers, San Francisco, second edition, 2000.

[36] A. Greenberg and N. Madras. How fair is fair queuing. In Proc.

Performance ’90, 1990.

[37] S.N. Bhatti and J. Crowcroft. Qos-sensitive flows: Issues in ip packet handling. IEEE Internet Computing, jul 2000.

[38] S.S kanhere, H. Sethu, and A.B. Parekh. Fair and efficient packet scheduling using elastic round robin. IEEE Transactions on Parallel and Distributed Systems, 13, mar 2002.

[39] H. Sariowan, R.L. Cruz, and G.C. Polyzos. Sced: A generalized schedu- ling policy for guaranteeing quality of service. IEEE/ACM Transactions on Networking, 7, oct 1999.

[40] R.L. Cruz. Sced+: Efficient management of quality of service guarantees. IEEE, feb 1998.

[41] G. W. Leibniz. Monadologia. R.C.S. Libri, Milano, i edizione bompiani testi a fronte edition, 2001.

[42] B. Caprita, W. Chun Chan, and J. Nieh. Group round robin: Improving

the fariness and complexity of packet scheduling. Technical report,

Department of Computer Science, Columbia University, jun 2003.

142 BIBLIOGRAFIA

[43] H. M. Chaskar and U. Madhow. Fair scheduling with tunable latency:

a round-robin approach. IEEE Transactions on Networking, 11, aug 2003.

[44] F. Baker, J. Heinanen, W. Weiss, and J. Wroklawsky. Assured forwarding phb (per hop behavior), June 1999.

[45] Ns home page: http://www.isi.edu/nsnam/ns/.

[46] N. Bonelli. Valutazione di prestazioni di architetture di router estensi- bili basate su piattaforma network processor. Master’s thesis, Facolt` a di ingegneria, Universit` a di Pisa, 2003.

[47] http://awgn.antifork.org.codes.

[48] http://netgroup-serv.iet.unipi.it.

[49] J. Schmitt, P. Hurley, M. Hollick, and R. Steinmetz. Per-flow guarantees under class-based priority queueing. IEEE, 2003.

[50] A. Charny and J.Y. Le Boudec. Delay bounds in a network with ag- gregate scheduling. In Workshop Quality of Future Internet Services (QofIS’2000). Berlin, Germany, Sept 2000.

[51] Y. Jiang. Delay bounds for a network of guaranteed rate servers with fifo aggregation. National University of Singapore, preprint, 2001.

[52] V. Firoiu, J.Y. Le Boudec, D. Towsley, and Z.-L. Zhang. Theories and

models for internet quality of service. In Proceedings of the IEEE, may

2002.