IS-IS routing protocol:

Final report (PDF file).

The purpose of this project is two fold: to implement a version of the IS-IS routing protocol and to (if possible) speed up the convergence of that protocol.

One of the major problems with implementing Quality of Service guarantees in the IP/Internet world is that the network responds relatively slowly (with respect to routing) to topology changes. Response time in a relatively small intranet is measured on the order of a few minutes. In the Internet in general the time is on the order of tens of minutes or longer. I would like to find ways to decrease the delay between the time when a topology change takes place and when the network finally stabilizes.

The project will have three phases.

Interconnected LANs with backbone ATM switches:

Presentation slides and final report (PDF files).

With the development of a wide range of network types, allowing a company to flexibly mix and match its LANs and servers to reflect changes in the organization and to embrace new technology. ATM is one of these new technologies and hubs based on ATM switches are now available that support both the interconnection of legacy LANs and ATM stations.

In our project, we are going to build an ATM backbone network which connects three different LANs: an Ethernet with topology of star, a token ring, and a FDDI.

We are going to simulate this network in Opnet, and investigate the message transforming within the same LAN and between different LANs. We plan to change some parameters, then collect some global information such as network delay, transformation reliability, and thus to prove the applicability of this interconnected network.

References:
[1] Hook your legacy LAN to ATM, Darling, Charles B. From: Datamation, 42, S'96, 98-103
[2] ATM backbones: complex? And how!, Strauss, Paul. From: Datamation, 40, Jl 15 '94, 44-6+
[3] Data communicating using ATM: architectures, protocols, and resource management, Fischer, Wolfgang, Wallmeier, Eugen, Worster, Thomas. From: IEEE Communications Magazine, 32, Ag '94, 24-33
[4] ATM local area networks: a survey of requirements, architectures, and standards, Akyildiz, Ian F., Bernhardt, Keith L. From: IEEE Communications Magazine, 35, Jl '97, 72-80
[5] LAN !V local area networking, Stone, Forrest. From Radio-Electronics, 57, Je '86, CD6-9
[6] ATM local area networks, Newman, Peter. From: IEEE Communications Magazine, 32, March '94, pp. 86-98
[7] Traffic management for ATM local area networks, Newman, Peter. From: IEEE Communication Magazine, 32, Aug '94, pp. 44-50

Performance of TCP protocol running over WLAN 802.11 with Performance Enhancing Proxy (PEP):

Presentation slides and final report (PDF files).

With the heavy usage of the TCP/IP protocol on the Internet and the growing popularity of using wireless devices to access the Internet, it is expected that TCP protocol will be frequently used over the wireless link connecting the wireless devices in the near future.

The connection characteristics (e.g. bit error rate) of the wireless link are significantly different from that of a wired line network because data are frequently lost due to the volatile environment that a wireless link operates. TCP is originally targeted towards a wired system, which assumes any loss of data is caused by congestion. This assumption leads to poor performance of TCP over wireless link. Therefore, a number of mechanisms are proposed by various research groups to improve TCP performance over wireless link. Implementing a Performance Enhancing Proxy (PEP) is one of the ways that has been proposed to improve the TCP performance over wireless link.

The first phase of the project will evaluate the TCP performance over WLAN 802.11 network using OPNET. The second phase will implement the PEP mechanism. The third phase will compare improvement in the TCP performance over the WLAN 802.11 network achieved by the PEP mechanism.

References:
[1] IEEE 802.11 Workgroup
[2] Performance Enhancing Proxy (PEP) Request for Comments (RFC)
[3] Improving TCP/IP Performance over Wireless Networks
[4] W.Richard Stevens, TCP/IP Illustrated Volume 1, Addison Wesley, Professional Computing Series, 1984.
[5] Andrew S. Tanenbaum, Computer Networks Third Edition, Prentice-Hall Press, 1996.

Wireless Ethernet performance:

Presentation slides and final report (PDF files).

The proposed project involves implementing a multi-user, wireless Ethernet (IEEE 802.11b) network and simulating the network performance when voice, data, and video traffic are simultaneously transmitted across the network. The goal of the project is to learn about the relatively new and popular short-range wireless networking technology, and what the practical applications are for its bandwidth and range limitation. Once the system has been implemented attempts will be made to tweak the performance and determine factors that affect QoS.

OPNET is the current simulation tool of choice. There is an existing Wireless Ethernet implementation in OPNET. Our task includes determining what is already implemented and what additional features can be added.

References:
[1] Al Petrick, "Standards & Protocols: IEEE 802.11b - Wireless Ethernet"
[2] OPNET technologies, Inc., "Wireless LAN Model Description"
[3] Editors of IEEE 802.11, "Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Std 802.11-1997", Institute of Electrical and Electronics Engineers, Inc. New York, 1997.
[4] Rusty O. Baldwin, Nathaniel J. Davis IV, Scott F. Midkiff, "Implementation of an IEEE 802.11 Wireless LAN Model using OPNET", Bradley Department of Electrical and Compluter Engineering, Virginia Polytechnic Institute and State University, 1998.
[5] Giuseppe Bianchi, "Performance Analysis of the IEEE 802.11 Distributed Coordination Function", IEEE Journal on Selected Areas in Communications, Vol. 18, No. 3, March 2000.
[6] Federico Cali, Marcho Conti, and Enrico Gregori, "IEEE 802.11 Protocol: Design and Performance Evaluation of an Adaptive Backoff Mechanism", IEEE Journal on Select4ed Areas in Communications, Vol. 18, No 9, September 2000.
[7] Linda D. Paulson, "Exploring the Wireless LANscape", IEEE Journal of Computer, Vol. 33, Issue 10, Page 12~16, October 2000.

Investigation and Enhancement of MPLS Congestion Management Control Strategies using CR-LDP:

Presentation slides and final report (PDF files).

Multi Protocol Label Switching (MPLS) was initially proposed to overcome the bottleneck of IP routing over ATM while retaining the efficiency of ATM's label swapping and forwarding abilities. Now with the advent of gigabit routers the issue of connection oriented forwarding and IP routing integration is more focused on the additional advantages that MPLS provides: to manage traffic not necessarily based on shortest path measures, to provide QoS routing, the ability to set up Virtual Private Networks (VPN) and to implement congestion management control strategies. One control standard that allows MPLS to provide QoS based routing is the Constraint based Routing Label Distribution Protocol.(CR-LDP). This project will set up a network using CR-LDP over UDP and investigate the ability of CR-LDP to reroute traffic based on flow considerations. The most promising congestion management strategies presently used will be investigated and enhancements will be proposed and modelled.

References:
[1] "Constraint-Based LSP Setup using LDP", IETF Internet Draft, July 2000. [http://search.ietf.org/internet-drafts/draft-ietf-mpls-cr-ldp-04.txt]
[2] "LDP State Machine", IETF Internet Draft, January 2000. [http://search.ietf.org/internet-drafts/draft-ietf-mpls-ldp-state-03.txt]
[3] B. Davie, P. Doolan & Y. Rekhter, "Switching in IP Networks: IP Switching, Tag Switching and Related Technologies, Morgan Kaufman Publishers, Inc., 1998.
[4] "Multiprotocol Label Switching Architecture", IETF Internet Request for Comments, RFC 3031, January 2001. [http://www.ietf.org/rfc/rfc3031.txt?number=3031]
[5] "LDP Specification", IETF Request for Comments, RFC 3036, January 2001. [http://www.ietf.org/rfc/rfc3036.txt?number=3036]
[6] T. Chen & T. Oh, "Reliable Services in MPLS", IEEE Communications Magazine, Vol.37, No.12, pp.58-62, December 1999.
[7] E. Lim, H. Shin, Y. Kim, "Implementation of the Simulation Model for the MPLS Signaling Protocol and OAM Functions With OPNET", [http://www.mil3.com/products/modeler/biblio.html]

QoS technology study: IntServ vs. DiffServ:

Presentation slides and final report (PDF files).

We plan to study and design Qos architecture models to provide different levels of services to different applications. Currently, there're two technologies for Qos: Integrated Services Archetecture(IntServ) and Differentiated Services Framework(DiffServ). We want to compare these two methods by simulating them using Opnet and analysis the collecting results.

References:

The Design, Implementation and Analysis of a Multicast System:

Presentation slides and final report (PDF files).

The multimedia services in the internet are in a great demand and also give much pressure on servers side's delivering streams. Traditionally, IP is the native protocol layer for multicast related functionality. However, this kind of IP multicast service is not very practical because it requires all the routers in the path supporting multicast function. Even in the view of today's internet status, most of the internet nodes which are commercial routers, still don't support such multicast protocol. In many cases, people have to replace routers with multicast protocol before accessing multicast system. Also the servers side's heavy amount of thrughput makes the quality of multicast service unsatisfactory. These reasons prevent multicast system to be fully used in the current internet. In order to solve the above problems, in this project, I want to try an alternative architecture, where end systems instead of infrastructural level routers implement all multicast related functionality including membership management and data replication and transmission. This end system multicast is constructed on the top of unicast services provided by network or transport layer. I will design a multicast membership management protocol, develop an end system multicast prototype, and use some software tools such as OPNET to analyze the system performance and scalability etc. (To demonstrate the end system multicasting function, I plan to use the video streaming as the data source to show that this method is efficient and effective).

References:

To understand Session Initiation Protocol:

Presentation slides and final report (PDF files).

Internet telephony is evolving from its use as a "cheap" way to make international phone calls to a serious business telephony capability. Supporting the widespread use of Internet telephony requires a host of standardized protocols to ensure quality of services (QoS), transport audio and video data, provide directory services, and enable signalling. Signalling protocols are of particular interest because they enable such advanced services as mobility, universal numbers, multiparty conferencing, voice mail, and automatic call distribution. Two signalling protocols have been emerged to fill this need: ITU H.323 and IETF Session Initiation Protocol (SIP). Analysts expect SIP to overpass H.323 in the next two years because of its strength - simplicity, scalability, extensibility, and modularity.

SIP is developed by Internet Engineering Task Force (IETF) and is modeled after the simple mail transfer protocol (SMTP) and the hypertext transfer protocol (HTTP). SIP is an application-layer control protocol for creating, modifying application-layer control protocol for creating, modifying and terminating sessions with one or more participants. These sessions include Internet multimedia conferences, Internet telephone calls and multimedia distribution.

In this project, we will implement SIP messages that are required for a basic session initiation, and SIP user agent. Due to the its complexity and tight schedule of the course, proxy/redirect server will not be implemented. All the SIP messages and user agent will be written in C. Several SIP calls will be simulated in order to demonstrate the functionality and capability of each SIP component. The intent deliverables include (1) source code of SIP messages and SIP user agent (both client and server); (2) design document with API specification; (3) SIP conformance specifications; (4) sample SIP message flow; (5) project presentation slides; (6) suggestions for future development.

The ultimate intent is to learn SIP which becomes one of the popular signalling protocols in VoIP arena, and of course to have some fun!

References:
[1] RFC 2543bis-02, SIP: Session Initiation Protocol, IETF, November 24, 2000.
[2] SIP Telephony Service Examples, IETF, November 2000.
[3] Henning G.Schulzinne and Jonathan D.Rosenberg, "The Session Initiation Protocol: Providing Advanced Telephony Services Across the Internet", Bell Labs Technical Journal, October-December 1998.
[4] "Overview of the SIP protocol", the SIP Center http://www.sipcenter.com/overview.htm
[5] SIP for Telephones (SIP-T): Context and Architectures, IETF, November 21, 2000.

Investigation and Implementation of Reliable Multicast Transport Protocols using ns-2:

Presentation slides and final report (PDF files).

Widespread availability of IP multicast has substantially increased the geographic span and portability of collaborative multimedia applications. Examples of such applications include distributed shared whiteboards, group editors, and distributed games or simulations. Such applications often involve many participants and typically require a specific form of multicast communication in which a single sender must reliably transmit data to multiple receivers. IP multicast provides scalable and efficient routing and delivery of IP packets to multiple receivers. However, it does not provide the reliability needed by these type of application.

Our goal is to exploit the highly efficient best-effort delivery mechanism of IP multicast to simulate several scalable and efficient transport protocols for reliable multicast. In this project, we implement and compare different flavors of multicast transport protocols, including Reliable Multicast Protocol, Tree-based Multicast Transport Protocol, and Scalable Reliable Multicast, using ns-2 simulator. We examine the performance, overhead, and scalability for each chosen protocols in campus network model. We use carefully chosen web and FTP background traffic to capture the characteristics of a real network environment. In addition, we use multimedia traffic traces to evaluate each chosen multicast transport protocol. Based on the simulation, we show the advantage and trade-offs for each of the multicast protocols.

References:
[1] M. Banikazemi. ``IP Multicasting: Concepts, Algorithms, and Protocols, IGMP, RPM, CBT, DVMRP, MOSPF, PIM, MBONE,''; http://charly.kjist.ac.kr/~dwlee/homepage/ipmulitcast.htm
[2] B. Williamson. ``Developing IP Multicasting Networks Volume 1 - Distance Vector Multicast Routing Protocol and Multicast Open Shortest Path First,'' pp. 106-127 pp.194-211, Cisco Press, 2000.
[3] E. C. Douglas, ``Internetworking with TCP/IP Volume 1 - Internet Multicasting (IGMP),'' pp. 289-302, Prentice-Hall, Inc., 1995.
[4] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. G. Liu, and L. Wei, ``An Architecture for Wide-Area Multicast Routing,'' ACM SIGCOMM '94, vol. 24 no. 4, pp. 126-135.
[5] S. Floyd, V. Jacobson, C.-G. Liu, S. McCanne. and L. Zhang. ``A Reliable Mulitcast Framework for Light-weight Sessions and Application Level Framing,'' ACM SIGCOMM? 95, Aug. 1995, pp. 342-356.
[6] S. Armstrong, A. Freier, K. Marzullo, ``RFC 1301: Multicast Transport Protocol,'' Feb. 1992, http://www.cis.ohio-state.edu/cgi-bin/rfc/rfc1301.html
[7] B. Whetten, G. Taskale. ``An Overview of Reliable Multicast Transport Protocol II,'' IEEE Network, Jan/Feb 2000, pp. 37-47; http://www.komunikasi.org/pdf/multicast/reliable-multicast-transport-protocol-ii.pdf
[8] M. T. Lucas, B. J. Dempsey, and A. C. Weaver. ?MESH: Distributed Error Recovery for Multimedia Streams in Wide-Area Multicast Networks,? In Proceedings of IEEE International Conference on Communication (ICC '97), pp. 1127-1132, June 1997.
[9] M. T. Lucas. ?Efficient Data Distribution in Large-Scale Multicast Networks,? Ph.D. Dissertation, Department of Computer Science, University of Virginia, May 1998.
[10] M. Goncalves and K. Niles, ``IP Multicasting, Concepts and Applications,'' New York: McGraw-Hill, 1998, pp. 91-116, pp. 273-287, pp. 305-324.
[11] ns-2 network simulator: http://www.isi.edu/nsnam/ns
[12] Star Wars trace in ns format: http://www.research.att.com/~breslau/vint/trace.html
[13] C. Hanle and M. Hofmann, ``Performance Comparison of Reliable Multicast Protocols using the Network Simulator ns-2,'' Proceedings of IEEE Conference on Local Computer Networks (LCN), Boston, MA, USA, October 11-14, 1998.
[14] V. Markovski, ``Simulation and Analysis of Loss in IP Networks - Simulation scenarios,'' M. Sci. Thesis, Department of Engineering Science, Simon Fraser University, Oct. 2000, pp. 24-30.
[15] R. Yavatkar, J. Griffioen, and M. Suda. ``A Reliable Dissemination Protocol for Interactive Collaborative Application,'' In Proceedings of the ACM Multimedia ?95 Conference, Nov. 1995.

Analysis of User Behaviour in a Cellular Digital Packet Data (CDPD) Network:

Presentation slides and final report (PDF files).

My project is to analyze a billing trace from a province-wide CDPD network to try to determine patterns of user behaviour. I will be attempting to use Autoclass to determine clustering in the data, but will also be gathering general statistics on the data - for example, proportion of rejected calls, proportion of calls that move from one cell to another, average duration of calls, average duration of calls per time of day, etc.

I will be looking for as many patterns as possible. For example, is a call more likely to be rejected if the user is not in his or her 'home' cell?

Although the data have been sanitized to protect the users' privacy, it has not been altered - patterns should still be detectable.

Project Plan:

Write a data parser in Java using Metamata parse to read the trace data into a generic model format.
Write the generic model into a format that Autoclass likes. Run Autoclass on the full data set to look for initial results.
Write out the generic model by Cell ID & search for classes among the cells.
Write out the generic model by 'user' ID & search for classes among users.
Attempt to 'discover' the network topology by finding pairs of cell IDs which have disconnection and connection commands in rapid sequence. (If time permits, write or find a visualization tool to display this.)
Write out the data per user in sequence, so we have a 'trace' of each user's activity.

Gather the following statistics and plot them (against each other where interesting):
- proportion of calls dropped
- packet size over time of day, average per user
- duration of calls
- proportion of control traffic relative to user traffic
- proportion of calls made from the user's 'home cell'

Write up.

References:
Tools
[1] http://java.sun.com/
[2] http://www.metamata.com/parse.html
[3] http://ic-www.arc.nasa.gov/ic/projects/bayes-group/autoclass/
[4] http://www.research.att.com/areas/stat/xgobi/
Theory
[5] Diane Tang and Mary Baker, "Analysis of a Local-Area Wireless Network," Proceedings of Mobicom 2000, Boston, August 2000. http://mosquitonet.stanford.edu/publications.html
[6] Diane Tang and Mary Baker, "Analysis of a Metropolitan-Area Wireless Network," Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom 1999), Seattle, Washington, August 1999. http://mosquitonet.stanford.edu/publications.html
[7] Experiences with a Mobile Testbed (1998) Kevin Lai, Mema Roussopoulos, Diane Tang, Xinhua Zhao, Mary Baker Stanford http://citeseer.nj.nec.com/101593.html
[8] A Tutorial on Learning Bayesian Networks (1995) David Heckerman http://citeseer.nj.nec.com/135897.html
[9] P. Cheeseman, J. Stutz, "Bayesian Classification (AutoClass): Theory and Results", in Advances in Knowledge Discovery and Data Mining, Usama M. Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth, & Ramasamy Uthurusamy, Eds. AAAI Press/MIT Press, 1996. http://ic-www.arc.nasa.gov/ic/projects/bayes-group/autoclass/autoclass-refs.html
[10] Anselm Linhnau, Oswald Drobnik "User Data Management for Mobile Communications An object oriented approach" Johann Wolfang Göthe-Universitaet Frankfurt http://mercan.cmpe.boun.edu.tr/~onure/paper_index.html
[11] Cem U. Saraydar, Christopher Rose "Location Area Design Using Population and Traffic Data" CISS 1998, March, 1998 http://mercan.cmpe.boun.edu.tr/~onure/paper_index.html
[12] Ivan Seskar, Svetislav Maric, Jack Holtman, Jack Wasserman "Rate of Location Area Updates in Cellular Systems" WINLAB May 92 - IEEE VTC, Dalas, May, 1992 http://mercan.cmpe.boun.edu.tr/~onure/paper_index.html

Implementation of IPv6's QoS over ATM Network:

Presentation slides (PDF file).

The goal of our project is to develop a general traffic client node with "smart" packet switching mechanism by merging IPv6 and the Asynchronous Transfer Mode (ATM) as the protocol for the QoS enabled Internet. By examining the "Type Of Service" field in the IPv6 packets, the general traffic client can channel different QoS packets onto the appropriate PVC/SVC which has matching QoS parameters. The IPv6 and ATM cell co-switching mechanism implemented by the general traffic client preserves the connectionless feature for non-realtime applications and provide the QoS for realtime applications through merging the IPv6 and ATM protocols. The application of Type Of Service on congestion control algorithm (such as establishing SVC dynamically in case of high QoS traffic experiences congestion) will also be examined in the course of the project if time permitted. The Opnet standard ATM model, in particular the raw packets over ATM model, will be employed as the starting point for our project.

References:
[1] IP Next Generation Overview
[2] IPv6: The New Internet Protocol
[3] G. Armitage, M. Jork, P. Schulter, G. Harter, IPv6 over ATM Networks, RFC2492, January 1999.
[4] Internet Protocol, Version 6 (IPv6) Specification. S. Deering, R. Hinden. RFC2460, December 1995.
[5] Asynchronous Transfer Mode (ATM) Switching
[6] Opnet ATM Model Description

Convergence behavior of routing protocol EIGRP:

Presentation slides and final report (PDF files).

Enhanced Interior Gateway Routing Protocol (EIGRP) is a Cisco proprietary routing protocol. It successfully addresses most network scalability needs. In addition, it is the only routing protocol that support IP, IPX and AppleTalk.

There are two sections in this project. The first half is the theory part. It introduces different kind of Interior Routing Protocol (e.g. RIP, IGRP, OSPF, EIGRP) and also the core of the EIGRP protocol: the Diffusing-Update Algorithm (DUAL). Second, several Cisco routers are used to simulate an industrial network running EIGRP (as shown in Fig. 1). Link failure behavior can be observed by disconnecting the link between Router4 and Router 5. Impact on the convergence behavior will be investigated too by modifying different parameters of the EIGRP (e.g. timers and the "K"s value).

References:
[1] Jeff Doyles, CCIE Professional Development: Routing TCP/IP, Vol. 1, Cisco Press, January 1998.
[2] Michael Saterlee, Stephen Hutnik, Cisco CCIE All-in-One Lab Study Guide Oracle Press, September 1999.
[3] Andrew Caslow, Cisco Certification: Bridges, Routers & Switches for CCIEs, Prentice-Hall Of Canada Ltd, December 1998.
[4] Enhanced Interior Gateway Routing Protocol (EIGRP)
[5] Introduction to Enhanced IGRP (EIGRP)
[6] Certification Zone (need log-in ID)

ATM Traffic Control Based on Cell Loss Priority and Performance Analysis:

Presentation slides and final report (PDF files).

ATM, a ultimate solution of B-ISDN to provide integrated multimedia services including voice, video and data, has entered into the limelight with increased demand for such services. Hence, ATM is to be capable of supporting a variety of service classes and providing appropriate QoS according to classes. This may force us to sacrifice low priority traffic classes for high priority traffic classes to satisfy the QoS requirements for the high priority traffic classes in case of congestion.

There have been many possibilities suggested for traffic control in terms of QoS and 'cell loss priority control', which was originally introduced in ATM networks for the purpose of congestion control, must be one of them. An application can offer two types of traffic streams to the ATM network. The cell loss priority (CLP) bit in the header of the ATM cell may be used to declare two levels of QoS. This CLP based cell loss priority control can be implemented by a variety of schemes. However, I will focus on three major methods; push-out, partial buffer sharing and separate buffer. In the push-out mechanism, the buffer accepts incoming cells until it becomes full and then rearranges them giving priority to high priority cells over low priority cells when new cells arrive. This is of high efficiency but has a disadvantage of complicated buffer management logic. In the partial buffer sharing, the buffer accepts high priority cells only once a reference queue size (threshold) is met. This mechanism has an advantage of simple implementation. Lastly, we may want have two separate buffers, one of which is for high priority cells and the other is for low priority cells, so as to make the cell loss ratio (CLR) of high priority cells as low as possible.

I will use Opnet to implement and simulate the above three methods and compare their performances in terms of critical parameters such as CLR and delay.

References:
[1] P.S. Neelakanta, "ATM Telecommunications," 2000.
[2] Guo-Liang Wu and Jon W. Mark, "A Buffer Allocation Scheme for ATM Networks: Complete Sharing Based on Virtual Partition," IEEE/ACM Transactions on Networking, Vol. 3, No. 6, December 1995.
[3] Dominique Gaiti and Guy Pujolle, "Performance Management Issues in ATM Networks: Traffic Congestion Control," IEEE/ACM Transactions on Networking, Vol. 4, No. 2, April 1996.
[4] Sridhar Ramesh, Gatherine Rosenberg and Anurag Kumar, "Revenue Maximization in ATM Networks Using the CLP Capability and Buffer Priority Management," IEEE/ACM Transactions on Networking, Vol. 4, No. 6, December 1996.
[5] Ness B. Shroff and Mischa Schwartz, "Improved Loss Calculations at an ATM Multiplexer", IEEE/ACM Transactions on Networking, Vol. 6, No. 4, August 1998.
[6] Todd Lizambri, Fernando Duran and Shukri Wakid, "Priority Scheduling and Buffer Management for ATM Traffic Shaping." http://w3.antd.nist.gov/Hsntg/publications/Papers/lizambri_1299.pdf
[7] Viet L. Do and Kenneth Y. Yun, "A Scalable Priority Queue Manager Architecture for Output-Buffered ATM Switches." http://paradise.ucsd.edu/PAPERS/ICCCN-99-PQM.pdf
[8] Space Priority Algorithms. http://www.dur.ac.uk/~des0www3/space/space2.html

Simulation in DSP network:

Presentation slides and final report (PDF files).

DSPs were first introduced in the early 1980s, the major type of application was to execute signal processing algorithms in software instead of hardware. DSPs have evolved from yesterday's signal processing engines to today's high performance CPUs with the capability to maintain several signal processing algorithms in parallel, in addition to a control application. Today's telecom systems often include a number of DSPs in a cluster (DSP farm) and a control processor. Since there is no standard operating system in DSP, it is often the case that engineer need to develop specific software for each application. One question follows this is how can we setup the structure and parameter in software so that they provide the best performance?

DSP world is very much like a computer network. It has the nodes - DSPs, the bus - PCI bus, VME bus, Expansion Bus with different speed. It has routers - one or two DSP will function like a actual router and pass data to different DSP to calculate according to algorithms and work load and queuing, congestion, flow controls. DSPs also have TCP/IP stacks on top of them.

If we look at one specific application to make it more clear. We may want to filter out all the packets for a special pattern, but we don't know the source and destination. We can put the devices in Data centers and filter out all incoming and outgoing packets in certain layer. Some DSPs will analyze one layer and pass to other DSPs the packets that matches for further investigation. How fast could DSPs do?

I plan to model the DSP network in a way that we model the computer network, apply one or two applications to see how the model works. This is useful for developing software on DSP, different algorithm can result in different performance.

Tool to be used: Opnet

References:
[1] E.A.Lee and D.G.Messerschmitt. ``Static scheduling of synchronous data flow programs for digital signal processing.'' IEEE Transactions on Computers, 1987 Jan, 36(1):24-35.
[2] E.A.Lee and D.G.Messerschmitt. Pipeline interleaved programmable DSPs: Synchronous Data Flow Programming. IEEE Transactions on Acoustics, Speech and Signal Processing, 1987, ASSP-35:1334-1345.
[3] W. A. Najjar, E. A. Lee, G. R. Gao, Advances in the dataflow computational model Parallel Computing, vol. 25 (1999) pp. 1907-1929.
[4] E. A. Lee and T. M. Parks, ``Dataflow Process Networks,'' Proceedings of the IEEE, vol. 83, no. 5, pp. 773-801, May, 1995.
[5] Guoning Liao, Guang R.Gao, Vinod K. Agarwal A Dynamically Scheduled Parallel DSP Architecture for Stream Flow Programing, ACAPS Technical Memo 45, June 4, 1993
[6] P. K. Murthy, Scheduling Techniques for Synchronous and Multidimensional Synchronous Dataflow, Technical Report UCB/ERL M96/79, Ph.D. Dissertation, EECS Department, University of California, Berkeley, CA 94720, December 1996.
[7] Shuvra S. Bhattacharyya, Praveen K. Murthy, and Edward A. Lee, `` Synthesis of Embedded Software from Synchronous Dataflow Specifications,'' Journal of VLSI Signal Processing Systems, Vol. 21, No. 2, June 1999.
[8] T. M. Parks, Bounded Scheduling of Process Networks, Technical Report UCB/ERL-95-105. Ph.D. Dissertation. EECS Department, University of California. Berkeley, CA 94720, December 1995.
[9] J. L. Pino, S.S. Bhattacharyya and E. A. Lee, A Hierarchical Multiprocessor Scheduling Framework for Synchronous Dataflow Graphs, UCB/ERL M95/36, May 30, 1995
[10] Timothy W.O'Neil, Edwin H.-M.Sha, Sissades Tongsima Parallelizing Synchronous Data-Flow Graphs via Retiming