Communication Networks Laboratory projects

ICON DAWN SIMON VARIOUS

Our research projects in the Communication Networks Laboratory at the School of Engineering Science at SFU deal with simulation and analysis of high-performance packet networks: traffic, protocols, and control algorithms.

Packet data networks, such as the Internet, are the infrastructure for delivering voice, data, and video applications. The quality of service that they deliver to users is a complex interaction of network traffic, protocols, and scheduling mechanisms employed in network elements (routers). Hence, evaluating network performance is a difficult task that is of importance both to service providers and network users.

Our projects deal with modeling and characterization of traffic emanating from interaction of voice, data, and video applications in IP (Internet Protocol) networks. In our laboratory, we use traffic traces from our own Mbone Webcast, from Internet Traffic Archive, and collections from CAIDA. In order to analyze network utilization and usage patterns, we also use billing records and traffic data collected from deployed networks: Telus Mobility (Vancouver), E-Comm (British Columbia), and ChinaSat (China). We analyze traffic traces, packet loss, and packet delay using mathematical tools, such as mono-fractal and multi-fractal wavelet analysis, in order to detect and quantitatively characterize the presence of long-range dependence (fractal behavior) in statistical processes emanating from Internet traffic.

We rely on simulation tools (ns-2 and OPNET) to evaluate performance of various wireline and wireless network protocols. We utilize traffic traces in various simulation scenarios (trace driven simulations) employing protocols such as Transmission Control Protocol and User Data Protocol. We use packet loss and packet delay as measures of network performance. Trace driven simulations using ns-2 and OPNET simulators are also employed to implement and evaluate performance of various scheduling and active control mechanisms. We are currently interested in using nonlinear dynamics and control theory to analyze network protocols and algorithms in order to better understand complex behavior, such as chaotic phenomena, already observed in IP networks.

Analysis of Traffic Data from Wireless and Wireline Networks

Machine learning for classifying anomalies and intrusions in communication networks
Zhida Li (Ph.D. student) and Ljiljana Trajkovic (supervisor)

Cyber attacks are becoming more sophisticated and, hence, more difficult to detect. Using efficient and effective machine learning techniques to detect network anomalies and intru- sions is an important aspect of cyber security. A variety of machine learning models have been employed to help detect malicious intentions of network users. In this dissertation, we have applied various machine learning algorithms to classify known network anomalies such as Internet worms, denial of service attacks, power outages, and ransomware attacks. We have proposed novel Broad Learning System-based algorithms with and without incremen- tal learning. Generalized models have been developed by using subsets of input data based on selected features and by expanding the network structure. Furthermore, a Border Gate- way Protocol anomaly detection tool BGPGuard has been developed to integrate various stages of the anomaly detection process.

BGP Feature Properties and Classification of Internet Worms and Ransomware Attacks
Hardeep Kaur Takhar (M. A. Sc. student) and Ljiljana Trajkovic (supervisor)

Machine learning approaches for anomaly detection heavily depend on the training data and their properties. In this project, we analyze the impact of data probability distribution on the performance of machine learning models developed based on worms and ransomware attack Border Gateway Protocol datasets. We perform feature selection to determine the most important features and identify the best fitting distributions. Experimental results indicate that a number of features follow heavy-tailed distributions. Classification of traffic anomalies is evaluated using the gradient boosting decision tree models that offer short training time thus being suitable for designing real-time and scalable intrusion detection systems.

Deep echo state networks for detecting Internet worm and ransomware attacks
Khushi Patni (B. Tech. student), Tarun Sharma (B. Tech. student), and Ljiljana Trajkovic (supervisor)

With the advancement of technology over the last decade, there has been a rapid increase in the number and types of malware attacks such as worms whose primary function is to self-replicate and infect systems and ransomware that corrupts and encrypts data. Developing proactive cyber defense techniques is essential for effectively detecting network anomalies that are evolving and becoming more challenging to identify. In this project, we consider intrusion detection techniques using fast machine learning algorithms. We investigate echo and deep echo state networks machine learning structures for detecting worm and ransomware anomalies. We demonstrate, analyze, and compare merits of this approach using Slammer worm, WannaCrypt ransomware, and WestRock ransomware attack datasets.

Detection of denial of service attacks using echo state networks
Kamila Bekshentayeva (M. A. Sc. student) and Ljiljana Trajkovic (supervisor)

Denial of Service and Distributed Denial of Service attacks are major threats to communication security. These cyber attacks are evolving and becoming more difficult to identify and, hence, a number of detection approaches have been proposed. Various machine learning techniques have proved useful in detecting network intrusions. We apply echo state networks to detect known DoS and DDoS attacks. Echo state networks are a reservoir computing approach to train recurrent neural networks. The reservoir in the echo state networks serves as a memory and as a nonlinear high dimensional expansion of the input. The performance of echo state network models depends on settings of reservoir hyperparameters: input scaling, spectral radius, leaking rate, size and sparsity of the reservoir, and distribution of nonzero elements. The most important features are selected using an extra-trees classifier. We use network intrusion and Internet routing datasets. We compare echo state network models to bidirectional long short-term memory, one of the widely used recurrent neural networks, and evaluate their performance based on accuracy, F-Score, false alarm rate, and training time.

Broad learning system for classifying network intrusions
Zhida Li (Ph.D. student), Ana Laura Gonzalez Rios (M.A.Sc. student), and Ljiljana Trajkovic (supervisor)

Detecting, analyzing, and defending against cyber threats is an important topic in cyber security. A variety of machine learning (ML) models have been designed to help detect malicious intentions of network users. Conventional ML techniques such as Support Vector Machine (SVM) and deep learning networks require long training time because of their high computational complexity and large number of hidden layers. An alternative to deep learning networks is the recently proposed Broad Learning System (BLS). BLS and its extensions offer comparable performance and shorter training time by using the single layer feedforward neural network (SLFN) architecture and pseudo-inverse to calculate output weights. We evaluate the effectiveness of the BLS and its extensions by employing datasets from the Canadian Institute for Cybersecurity Intrusion (CIC) Detection System (CICIDS2017) and the collaborative project between the Communications Security Establishment (CSE) and the CIC (CSE-CIC-IDS2018) containing DoS attacks. The algorithms are compared based on accuracy, F-Score, and training time.

  • Paper: A. L. Gonzalez Rios, Z. Li, G. Xu, A. Diaz Alonso, and Lj. Trajkovic, "Detecting network anomalies and intrusions in communication networks," in Proc. 23rd IEEE International Conference on Intelligent Engineering Systems 2019, Godollo, Hungary, April 2019, pp. 29-34.
  • Presentation: A. L. Gonzalez Rios, Z. Li, G. Xu, A. Diaz Alonso, and Lj. Trajkovic, "Detecting network anomalies and intrusions in communication networks," in Proc. 23rd IEEE International Conference on Intelligent Engineering Systems 2019, Godollo, Hungary, April 2019, pp. 29-34.

    • Machine learning techniques for classifying network anomalies and intrusions
    Zhida Li (Ph.D. student) and Ljiljana Trajkovic (supervisor)

    Cyber attacks are becoming more sophisticated and, hence, more difficult to detect. Using efficient and effective machine learning techniques to detect network anomalies and intrusions is an important aspect of cyber security. A variety of machine learning models have been employed to help detect malicious intentions of network users. In this project, we have applied various machine learning algorithms to classify known network anomalies such as Internet worms, denial of service attacks, power outages, and ransomware attacks. We have proposed novel Broad Learning System-based algorithms with and without incremental learning. Generalized models have been developed by using subsets of input data based on selected features and by expanding the network structure. Furthermore, a Border Gateway Protocol anomaly detection tool BGPGuard has been developed to integrate various stages of the anomaly detection process.

  • Paper: Z. Li, A. L. Gonzalez Rios, and Lj. Trajkovic, "Machine learning for detecting the WestRock ransomware attack using BGP routing records," IEEE Communications Magazine, vol. 61, no. 3, pp. 20-26, Mar. 2023.
  • Paper: Z. Li, A. L. Gonzalez Rios, and Lj. Trajkovic, "Classifying denial of service attacks using fast machine learning algorithms," in Proc. IEEE International Conference on Systems, Man, and Cybernetics, Melbourne, Australia, Oct. 2021, pp. 1221-1226 (virtual).
  • Paper: Z. Li, A. L. Gonzalez Rios, and Lj. Trajkovic, "Machine learning for detecting anomalies and intrusions in communication networks," IEEE Journal on Selected Areas in Communications, vol. 39, no. 7, pp. 2254-2264, July 2021.
  • Paper: Z. Li, A. L. Gonzalez Rios, and Lj. Trajkovic, "Detecting Internet worms, ransomware, and blackouts using recurrent neural networks," in Proc. IEEE International Conference on Systems, Man, and Cybernetics, Toronto, Canada, Oct. 2020, pp. 2165-2172 (virtual).
  • Presentation: Z. Li, A. L. Gonzalez Rios, and Lj. Trajkovic, "Detecting Internet worms, ransomware, and blackouts using recurrent neural networks," IEEE International Conference on Systems, Man, and Cybernetics, Toronto, Canada, Oct. 2020 (presentation video) (virtual).
  • Paper: A. L. Gonzalez Rios, Z. Li, K. Bekshentayeva, and Lj. Trajkovic, "Detection of denial of service attacks in communication networks," in Proc. IEEE Int. Symp. Circuits and Systems, Seville, Spain, Oct. 2020 (virtual).
  • Paper: Z. Li, A. L. Gonzalez Rios, G. Xu, and Lj. Trajkovic, "Machine learning techniques for classifying network anomalies and intrusions," in Proc. IEEE Int. Symp. Circuits and Systems, Sapporo, Japan, May 2019, pp. 1-5.
  • Presentation: Z. Li, A. L. Gonzalez Rios, G. Xu, and Lj. Trajkovic, "Machine learning techniques for classifying network anomalies and intrusions," in Proc. IEEE Int. Symp. Circuits and Systems, Sapporo, Japan, May 2019.
  • Paper: A. L. Gonzalez Rios, Z. Li, G. Xu, A. Diaz Alonso, and Lj. Trajkovic, "Detecting network anomalies and intrusions in communication networks," in Proc. 23rd IEEE International Conference on Intelligent Engineering Systems 2019, Godollo, Hungary, April 2019, pp. 29-34.
  • Paper: Z. Li, P. Batta, and Lj. Trajkovic, "Comparison of machine learning algorithms for detection of network intrusions," IEEE International Conference on Systems, Man, and Cybernetics (SMC 2018), Miyazaki, Japan, Oct. 2018, pp. 4238-4243.
  • Poster: Z. Li, P. Batta, and Lj. Trajkovic, "Comparison of machine learning algorithms for detection of network intrusions," IEEE International Conference on Systems, Man, and Cybernetics (SMC 2018), Miyazaki, Japan, Oct. 2018 (poster session paper).
  • Book chapter: Q. Ding, Z. Li, S. Haeri, and Lj. Trajkovic, "Application of machine learning techniques to detecting anomalies in communication networks: datasets and feature selection algorithms," in Cyber Threat Intelligence, M. Conti, A. Dehghantanha, and T. Dargahi, Eds., Berlin: Springer, 2018, pp. 47-70.
  • Book chapter: Z. Li, Q. Ding, S. Haeri, and Lj. Trajkovic, "Application of machine learning techniques to detecting anomalies in communication networks: classification algorithms," in Cyber Threat Intelligence, M. Conti, A. Dehghantanha, and T. Dargahi, Eds., Berlin: Springer, 2018, pp. 71-92.
  • P. Batta, M. Singh, Z. Li, Q. Ding, and Lj. Trajkovic, "Evaluation of support vector machine kernels for detecting network anomalies," in Proc. IEEE Int. Symp. Circuits and Systems, Florence, Italy, May 2018, pp. 1-4.
  • Q. Ding, Z. Li, P. Batta, and Lj. Trajkovic, "Detecting BGP anomalies using machine learning techniques," in Proc. IEEE International Conference on Systems, Man, and Cybernetics, Budapest, Hungary, Oct. 2016, pp. 3352-3355 (poster session paper).

    • Detecting BGP anomalies using machine learning techniques
    Qingye Ding (Ph.D. student), Zhida Li (Ph.D. student), Prerna Batta (M.A.Sc. student), and Ljiljana Trajkovic (supervisor)

    Border Gateway Protocol (BGP) anomalies affect network operations and, hence, their detection is of interest to researchers and practitioners. Various machine learning techniques have been applied for detection of such anomalies. We employ the minimum Redundancy Maximum Relevance (mRMR) and Decision Tree feature selection algorithms to extract the most relevant features used for classifying BGP anomalies and then apply the Support Vector Machine (SVM) and Long Short-Term Memory (LSTM) algorithms for data classification. We evaluate performance of SVM with linear, quadratic, and cubic kernels. The SVM kernels are compared based on accuracy and the F-Score when detecting BGP anomalies in Internet traffic traces. LSTM classifiers were implemented using the unbalanced and balanced datasets with 37 features. We compared LSTM classification results to SVM, Naļive Bayes, Decision Tree, and ELM results based on accuracy and F-score. The performance of classifiers heavily depends on the employed datasets, selected features, and their combinations. While no single classifier performs the best across all used datasets, machine learning has been shown to be a feasible approach to successfully classify BGP anomalies using various classification models.

  • Qingye Ding's M.A.Sc. thesis: "Application of machine learning techniques for detecting anomalies in communication networks" and presentation slides, June 2018.
  • Book chapter: Q. Ding, Z. Li, S. Haeri, and Lj. Trajkovic, "Application of machine learning techniques to detecting anomalies in communication networks: datasets and feature selection algorithms," in Cyber Threat Intelligence, M. Conti, A. Dehghantanha, and T. Dargahi, Eds., Berlin: Springer, pp. 47-70, 2018.
  • Book chapter: Z. Li, Q. Ding, S. Haeri, and Lj. Trajkovic, "Application of machine learning techniques to detecting anomalies in communication networks: classification algorithms," in Cyber Threat Intelligence, M. Conti, A. Dehghantanha, and T. Dargahi, Eds., Berlin: Springer, pp. 71-92, 2018.
  • Paper: P. Batta, M. Singh, Z. Li, Q. Ding, and Lj. Trajkovic, "Evaluation of support vector machine kernels for detecting network anomalies," IEEE Int. Symp. Circuits and Systems, Florence, Italy, May 2018, pp. 1-4.
  • Presentation: P. Batta, M. Singh, Z. Li, Q. Ding, and Lj. Trajkovic, "Evaluation of support vector machine kernels for detecting network anomalies," Proc. IEEE Int. Symp. Circuits and Systems, Florence, Italy, May 2018, pp. 1-4.
  • Paper: Q. Ding, Z. Li, P. Batta, and Lj. Trajkovic, "Detecting BGP anomalies using machine learning techniques," in Proc. IEEE International Conference on Systems, Man, and Cybernetics (SMC 2016), Budapest, Hungary, Oct. 2016, pp. 3352-3355.
  • Poster: Q. Ding, Z. Li, P. Batta, and Lj. Trajkovic, "Detecting BGP anomalies using machine learning techniques," in Proc. IEEE International Conference on Systems, Man, and Cybernetics (SMC 2016), Budapest, Hungary, Oct. 2016, pp. 3352-3355.

    • Using machine learning techniques to infer connectivity of social networks
    Qingye Ding (Ph.D. student), Zhida Li (Ph.D. student), and Ljiljana Trajkovic (supervisor)

    Internet is a collection of various Autonomous Systems (ASes). A detailed and accurate graph of the Internet topology is essential for network research. However, mapping a realistic Internet graph has been a challenge. In this project, we study the power-law and dynamic properties of AS-level Internet. We also use machine learning techniques including a deep neural network to predict the connectivity within social networks and relationships among various ASes.

    Classification of BGP anomalies using decision trees and fuzzy rough sets
    Yan Li, Hong-Jie Xing, Qiang Hua, Xi-Zhao Wang, Prerna Batta (M. A. Sc. student), Soroush Haeri (Ph. D. student), and Ljiljana Trajkovic (supervisor)

    Border Gateway Protocol (BGP) is the core component of the Internet's routing infrastructure. Abnormal routing behavior impairs global Internet connectivity and stability. Hence, designing and implementing anomaly detection algorithms is important for improving performance of routing protocols. While various machine learning techniques may be employed to detect BGP anomalies, their performance strongly depends on the employed learning algorithms. These techniques have multiple variants that often work well for detecting a particular anomaly. In this paper, we use the decision tree and fuzzy rough set methods for feature selection. Decision tree and extreme learning machine classification techniques are then used to maximize the accuracy of detecting BGP anomalies. The proposed techniques are tested using Internet traffic traces.

  • Paper: Y. Li, H. J. Xing, Q. Hua, X.-Z. Wang, P. Batta, S. Haeri, and Lj. Trajkovic, "Classification of BGP anomalies using decision trees and fuzzy rough sets," in Proc. IEEE International Conference on Systems, Man, and Cybernetics (SMC 2014), San Diego, CA, Oct. 2014, pp. 1312-1317.
  • Presentation: Y. Li, H. J. Xing, Q. Hua, X.-Z. Wang, P. Batta, S. Haeri, and Lj. Trajkovic, "Classification of BGP anomalies using decision trees and fuzzy rough sets," in Proc. IEEE International Conference on Systems, Man, and Cybernetics (SMC 2014), San Diego, CA, Oct. 2014, pp. 1312-1317.

    • Algorithms and tools for traffic anonymization
    Tanjila Farah (M. A. Sc. student) and Ljiljana Trajkovic (supervisor)

    Collecting network traffic traces from deployed networks is one of the basic steps in understanding communication networks. These traces may be used for network management, traffic engineering, packet classification, and for analyzing network behavior to ensure adequate Quality of Service. They may also be used for identifying and tracking network anomalies and formulating responses to maintain network security. For privacy and security reasons, monitored traffic traces should be modified before they may be shared. This is known as a trace anonymization process. The goal of anonymization is to preserve traffic properties while enforcing the privacy policies. Numerous tools and techniques have been implemented for trace anonymization such as Crypto-PAn, Anontool, ip2anonip, LucentĀ’s extensions to Crypto-PAn, FLAIM, IP-Anonymous, and TCPdprive. These tools use a variety of anonymization algorithms: black-marker, random permutations, truncation, pseudo-anonymization, and prefix-preserving pseudo-anonymization. We plan to evaluate performance of these anonymization tools and the impact of the anonymization algorithms on the anonymized traffic data.

  • Paper: T. Farah and Lj. Trajkovic, "Anonym: a tool for anonymization of the Internet traffic," in Proc. 2013 IEEE International Conference on Cybernetics (CYBCONF 2013), Lausanne, Switzerland, June 2013, pp. 261-266.
  • Presentation: T. Farah and Lj. Trajkovic, "Anonym: a tool for anonymization of the Internet traffic," 2013 IEEE International Conference on Cybernetics (CYBCONF 2013), Lausanne, Switzerland, June 2013, pp. 261-266.
  • T. Farah's M.A.Sc. thesis: "Algorithms and tools for anonymization of the Internet traffic" and presentation slides, Feb. 2013.

    • Comparison of machine learning models for classification of BGP anomalies
    Nabil Al-Rousan (M. A. Sc. student) and Ljiljana Trajkovic (supervisor)

    Worms such as Slammer, Nimda, and Code Red I are anomalies that affect performance of the global Internet Border Gateway Protocol (BGP). BGP anomalies also include Internet Protocol (IP) prefix hijacks, miss-configurations, and electrical failures.

    Statistical and machine learning techniques have been recently deployed to classify and detect BGP anomalies. In this research project, we introduce new classification features and apply Support Vector Machine (SVM) models and Hidden Markov Models (HMMs) to design anomaly detection mechanisms. We apply these multi-classification models to correctly classify test datasets and identify the correct anomaly types. The proposed models are tested with collected BGP traffic traces and are employed to successfully classify and detect various BGP anomalies.

    We also propose a Naive Bayes (NB) classifier for detecting the Internet anomalies using the BGP routing information base. Accuracy of a classifier depends on extracted features and the combination of features used to develop the detection model. Hence, in NB classifier, we emphasize feature selection process rather than the classification model. We compare the Fisher, minimum redundancy maximum relevance (mRMR), extended/multi-class/weighted odds ratio (EOR/MOR/WOR), and class discriminating measure (CDM) feature selection algorithms. We enhance the odds ratio algorithms to include both continuous and discrete features. The NB classifier using the extend selection algorithms achieved the highest scores.

  • N. Al-Rousan, S. Haeri, and Lj. Trajkovic, "Feature selection for classification of BGP anomalies using Bayesian models," in Proc. ICMLC 2012, Xi'an, China, July 2012.
  • N. Al-Rousan and Lj. Trajkovic, "Machine learning models for classification of BGP anomalies," in Proc. IEEE Conference on High Performance Switching and Routing, HPSR 2012, Belgrade, Serbia, June 2012, pp. 103-108.
  • Nabil Al-Rousan's M.A.Sc. thesis: "Comparison of machine learning models for classication of BGP anomalies" and presentation slides, Aug. 2012.

    • Collection and characterization of BCNET BGP traffic
    Sukhchandan Lally (M. A. Sc. student) and Ljiljana Trajkovic (supervisor)

    Measuring and monitoring traffic in deployed communication networks is necessary for effective network operations. Traffic analysis allows network operators to understand the network users behaviour and ensure quality of service (QoS). In this project, we described collection and analysis of BCNET BGP traffic. Border Gateway Protocol (BGP) is an Inter-Autonomous System routing protocol that operates over the reliable Transmission Control Protocol (TCP). The BCNET traffic was collected using special purpose hardware: the Net Optics Director 7400 and the Endace DAG 5.2X card. The collected data is analyzed using the Wireshark and Walrus graph visualization tools.

    The collected data will be used to analyze performance of the BGP protocol and the effect of route flaps and parameters such as minimal route advertisement interval (MRAI). BGP route flaps refer to persistent routing oscillations caused by network instabilities such as configuration errors, transient data, link failures, and software defects. Collected BGP traffic data may also be used to infer the Internet topologies and their historical development on AS level.

  • S. Lally, T. Farah, R. Gill, R. Paul, N. Al-Rousan, and Lj. Trajkovic, "Collection and characterization of BCNET BGP traffic," in Proc. 2011 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, Victoria, BC, Canada, Aug. 2011, pp. 830-835.
  • T. Farah, S. Lally, R. Gill, N. Al-Rousan, R. Paul, D. Xu, and Lj. Trajkovic, "Collection of BCNET BGP traffic," in Proc. 23rd International Teletraffic Congress, San Francisco, CA, Sept. 2011, pp. 322-323 (students poster session paper).
  • Sukhchandan Lally's M.A.Sc. thesis: "Collection and characterization of BCNET BGP traffic" and presentation slides, May 2012.

    • Modeling and characterization of traffic in public safety wireless networks
    Bozidar Vujicic (M. A. Sc. student), Nikola Cackov (M. A. Sc. student), Svetlana Vujicic (M. A. Sc. student), and Ljiljana Trajkovic (supervisor)

    This project deals with statistical analysis of traffic in a deployed circuit-switched, trunked radio cellular wireless network used by public safety agencies in Greater Vancouver Regional District. Traffic data span various time periods in 2001, 2002, and 2003. The statistical distribution and autocorrelation function of call inter-arrival and call holding times during several busy hours is examined. The call inter-arrival times are long-range dependent and may be modelled by both Weibull and gamma distributions. Call holding times follow the lognormal distribution and are uncorrelated. These findings indicate that traditional Erlang models for voice traffic may not be suitable for evaluating the performance of trunked radio networks. In addition, channel utilization and multi system call behaviour of trunked radio network have been simulated using OPNET. The instantaneous utilization of radio channels (the number of occupied radio channels) in each cell were examined in order to observe the traffic change over the period of two years and to predict future performance of the network.

  • B. Vujicic, H. Chen, and Lj. Trajkovic, ''Prediction of traffic in a public safety network,'' Proc. IEEE Int. Symp. Circuits and Systems, Kos, Greece, May 2006, pp. 2637-2640.
  • N. Cackov, J. Song, B. Vujicic, S. Vujicic, and Lj. Trajkovic, ''Simulation and performance evaluation of a public safety wireless network: case study,'' Simulation, vol. 81, no. 8, pp. 571-585, Aug. 2005.
  • B. Vujicic, N. Cackov, S. Vujicic, and Lj. Trajkovic ''Modeling and characterization of traffic in public safety wireless networks,'' Proc. SPECTS 2005, Philadelphia, PA, July 2005, pp. 214-223.
  • N. Cackov, B. Vujicic, S. Vujicic, and Lj. Trajkovic, ''Using network activity data to model the utilization of a trunked radio system,'' (special session) Proc. SPECTS 2004, San Jose, CA, July 2004, pp. 517-524.
  • Bozidar Vujicic's M.A.Sc. thesis: "Modeling and characterization of traffic in a public safety wireless network" and presentation slides, Nov. 2006.

    • Data mining on billing traces of wireless network
    Hao (Leo) Chen (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Billing records generated for thousands of users of a telecommunication network are a gold mine to the network service providers, for both business and technical usages. However, how to mine the "golden nugget" from the enormous amount of data is not an easy task.

    This research project deals with the billing record of a genuine wireless network. We plan to apply data mining technology on the real network data, and to develop new algorithm for clustering user groups or mobility patterns. The challenges of this task lay in the very nature of the network billing data: high dimensionality of data requires more computing power and efficient algorithm, temporal and spatial data require special treatment, while the clustered user groups require reasonable descriptions for better understanding by marketing experts.

    We work with the genuine billing records collected from the Telus Mobility CDPD (Cellular Digital Packet Data) network. These network data are more typical than data obtained via simulations. The records were collected in various intervals, from several hours to of almost 20 days. Prior study of these records dealt with the discovery of network topology by identifying ''neighboring'' cells and with clustering of user groups employing AutoClass. We plan to extend the analysis of records by developing novel and viable methods for extracting useful knowledge particular for the telecommunication network, by constructing clustering algorithm specialized for network data, and by giving an understandable representation of network characteristics. Our approach could help network service providers to identify hidden user groups and to understand the mobility characteristics of the existing and potential customers in order to optimize the wireless networks and expand the business markets.

  • H. Chen and Lj. Trajkovic, ''Trunked radio systems: traffic prediction based on user clusters,'' Proc. IEEE ISWCS 2004, Mauritius, Sept. 2004, pp. 76-80.
  • Hao (Leo) Chen's M. A. Sc. thesis: ''User clustering and traffic prediction in a trunked radio system'' and presentation slides, February 2005.

    Modeling and performance analysis of public safety wireless networks
    James (Jiaqing) Song (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Public safety wireless networks (PSWNs) play a vital role in operations of emergency agencies such as police and fire departments. In this thesis, we describe analysis and modeling of traffic data collected from the Emergency Communications for Southwestern British Columbia (E-Comm) PSWN.

    We analyze network and agency call traffic and find that lognormal distribution and exponential distribution are adequate for modeling call holding time and call inter-arrival time, respectively. We also describe a newly developed wide area radio network simulator, named WarnSim. We use WarnSim simulations to validate the proposed traffic model, evaluate the performance of the E-Comm network, and predict network performance in cases of traffic increase.

  • WarnSim simulator (developed by J. Song): Wide Area Radio Network Simulator.
  • J. Song and Lj. Trajkovic, ''Modeling and performance analysis of public safety wireless networks,'' Proc. IEEE Int. Performance, Computing, and Communications Conference, Phoenix, AZ, Apr. 2005, pp. 567-572.
  • J. Song and Lj Trajkovic, "Modeling and performance analysis of public safety wireless networks," IEEE Int. Performance, Computing, and Communications Conference, Phoenix, AZ, Apr. 2005. Presented by N. Cackov.
  • Jiaqing (James) Song, M. Sc. thesis: ''Modeling and performance analysis of public safety wireless networks'' and presentation slides, January 2005.

    Adapting ad hoc network concepts to land mobile radio systems
    Duncan Sharp (M. Eng. student) and Dr. Ljiljana Trajkovic (supervisor)

    Ad hoc networks are self organizing networks and require no prior infrastructure, which makes them robust and quick to deploy. These are good attributes for use by emergency response and disaster recovery teams. These teams coordinate their work by conversing on a common voice channel. Unfortunately, multicast voice is not well supported using current protocols for ad hoc multi hop networks. In this project, we analyze the traffic requirements (using real traffic from a large public safety agency radio system) and investigate the issues associated with carrying this type of traffic on single hop and multi hop ad hoc networks.

    The overall objective of the project is to identify evolving technologies, algorithms, protocols, and architectures for mobile ad hoc networks that are applicable, appropriate, and ready to be adopted by next generation land mobile radio systems and, in particular, by mobile radio systems designed for public safety communications applications.

  • D. Sharp, N. Cackov, N. Laskovic, Q. Shao, and Lj. Trajkovic, ''Analysis of public safety traffic on trunked land mobile radio systems,'' IEEE J. Select. Areas Commun., vol. 22, no. 7, Sept. 2004, pp. 1197-1205.
  • Duncan Sharp's M.Eng. project: ''Adapting ad hoc network concepts to land mobile radio systems'' and presentation slides, December 2002.

    Wavelet-based analysis of long-range dependent video traces
    Nikola Cackov (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Analysis of network traffic is important because a network behavior is determined by the characteristics of the traffic that it carries. In order to evaluate the effect of the network on various applications, it is essential to determine relevant traffic parameters. It is well known that network traffic exhibits phenomena known as self-similarity and long-range dependence. Self-similar and long-range dependent processes are classes of random processes characterized by a parameter, called Hurst parameter. There are several methods for estimation of the Hurst parameter of a given traffic trace, one of which is the wavelet-based method.

    Wavelet estimator is considered to be a very robust and unbiased. However, this estimator yields non-physical results when applied to MPEG-1 and MPEG-4 encoded video sequences. It has already been shown that these traffic traces exhibit long-range dependence. The main objective of the project is to discover the cause for the unreliable performance of the estimator. We observed that, for the video traces, estimators of the Hurst parameter that work in the frequency domain (wavelet-based and periodogram) produce similar results. However, the estimates are always larger than those obtained using time-domain estimators (R/S and variance-time plot). These findings may suggest that the relationship between the Hurst parameter and the exponent alpha of the power-law shaped spectrum is different than the widely-accepted H=0.5(alpha+1).

  • N. Cackov, Z. Lucic, M. Bogdanov, and Lj. Trajkovic, ''Wavelet-based estimation of long-range dependence in MPEG video traces,'' Proc. IEEE Int. Symp. Circuits and Systems, Kobe, Japan, May 2005, pp. 2068-2071.
  • Nikola Cackov's M. A. Sc. thesis: ''Wavelet-based estimation of long-range dependence in video and network traffic traces'' and presentation slides, December 2004.

    Wavelet analysis of traffic traces and packet loss
    Zelimir Lucic (M. Eng. student), Dr. Fei Xue (Postdoctoral fellow), Velibor Markovski (M. A. Sc. student), Bruce Chen (B. A. Sc. student), and Dr. Ljiljana Trajkovic (supervisor)

    We are investigating the performance of the Abry-Veitch wavelet-based estimator for the estimation of the Hurst parameter used in characterizing self-similar traffic. Performance results for two Ethernet traffic traces (pAug.TL, pOct.TL) indicate that the estimator can accurately capture Hurst parameter of the measured Ethernet traffic. In order to investigate the impact of long-range dependent (LRD) and short-range dependent (SRD) structures on the quality of the estimator, we apply the estimator on large sets of data generated by FARIMA(1,d,0) model. The performance analysis indicates that this estimator is not suitable for processes with strong SRD and either weak or strong LRD components. We confirm our findings by analyzing a medium-bursty Star Wars video traffic trace. Our findings imply that the estimator proves unsuitable for the medium- and high-burstiness video traffic because of the complex correlation structure of the video traces.

    We also use the Abry-Veitch estimator to investigate the scaling behavior of packet loss in video transfer over UDP and TCP in a congested packet network. Using trace-driven ns-2 simulations and wavelet analysis, we show that the underlying transport protocols and time scales are essential for understanding packet loss behavior. In the case of UDP transfers, packet loss process exhibits LRD over time scales coarser than approximately 1 second. In contrast, for the TCP transfers, the loss behavior over a coarser time scale does not exhibit such behavior. We attribute this phenomenon to the feedback control mechanisms in TCP, which decrease the burstiness of packet loss. Our findings are robust and hold for various simulation scenarios.

    We compared the performance of two wavelet based estimators: monofractal and multifractal, introduced by Abry and Veitch. The multifractal property of self-similar traffic implies that self-similarity still exists, but it is not uniform across all time scales. We use MPEG1, MPEG4, and H263 coded traffic video traces to compare the H parameter estimated using the wavelet based estimators, with the H parameter estimated via classical statistical methods, such as R/S. We are searching for the criteria for reliability of these two estimators. Our findings indicate that performance of both estimators is affected by the presence of SRD, but the effect of SRD is different for each estimator. It is interesting to note that graphical representations of the two wavelet based estimators are quite similar, while their numerical estimates of the H parameter tends to vary significantly.

  • V. Markovski, F. Xue, and Lj. Trajkovic, ''Simulation and analysis of packet loss in video transfers using User Datagram Protocol,'' The Journal of Supercomputing, Kluwer, vol. 20, no. 2, pp. 175-196, 2001.
  • F. Xue and Lj. Trajkovic, ''Performance analysis of a wavelet-based Hurst parameter estimator for self-similar network traffic,'' Proc. SPECTS '2K, Vancouver, BC, Canada, July 2000, pp. 294-298.
  • F. Xue, V. Markovski, and Lj. Trajkovic, ''Wavelet analysis of packet loss in video transfers over UDP,'' Proc. Internet Computing 2000, Las Vegas, NV, June 2000, pp. 427-433.
  • B. Chen, Z. Lucic, and Lj. Trajkovic, ''Simulation and wavelet analysis of the packet traffic,'' The ASI Exchange, Vancouver, BC, Canada, March 2002.
  • V. Markovski and F. Xue, ''Analysis of packet loss in IP networks,'' The ASI Exchange, Vancouver, BC, Canada, March 2000.

    TCP session analysis and modeling of hybrid satellite-terrestrial Internet traffic
    Savio Lau (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Satellite networks have received much attention in traffic analysis due to its loss characteristics and high bandwidth-delay product. Based on traffic traces collected from a commercial hybrid satellite network, I plan to examine traffic data at the session and packet levels. I will focus on the comparison of TCP modifications in the deployed network with proposals from research literature. Furthermore, I plan to analyze and model captured traffic on the packet level segmented by applications.

    Measurement and analysis of hybrid satellite-terrestrial Internet traffic
    Kenny Shao (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Measurement and analysis of genuine network traffic is important for traffic characterization. Collection and characterization of the terrestrial Internet traffic has received considerable attention during the past decade. Numerous web-sites offer collected samples of Internet traffic traces. To the contrary, few traffic traces have been collected from satellite/wireless commercial sites. We plan to collect hybrid satellite-terrestrial traffic traces from a commercial Internet access provider. The project objective is to model and analyze these traffic traces and to characterize the underlying processes and distributions.

  • Q. Shao and Lj. Trajkovic, ''Measurement and analysis of traffic in a hybrid satellite-terrestrial network,'' Proc. SPECTS 2004, San Jose, CA, July 2004, pp. 329-336.
  • Qing (Kenny) Shao's M. A. Sc. thesis: ''Measurement and analysis of traffic in a hybrid satellite-terrestrial network'' and presentation slides, April 2004.

    Spectral analysis of the Internet topology
    Hao (Johnson) Chen (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Discovering the properties of the Internet topology is crucial for the use, optimization, and maintenance of Internet. It is also essential for the improvement of network topology generators. Two recent approaches have dominated the research community: one based on data collected from active probing of hosts, and another based on Autonomous System (AS) topology information derived from Border Gateway Protocol (BGP) snapshots. Important rules, such as power-law distribution in AS graphs, have been discovered. The goal of our research is to qualify these two approaches and to find new valuable 1insights during the evaluation process.

    We use data from CAIDA (Cooperative Association for Internet Data Analysis) and from Route Views project at the University of Oregon. We employ Normalized Laplacian Spectrum (NLS) from spectral graph theory, because NLS proved to be unique in AS graphs in spite of the exponential growth of the Internet, and distinctive in setting AS graphs apart from synthetic ones. By applying NLS to the two datasets, we expect to obtain plausible interpretations in networking terms and a hybrid model encompassing both structural and power-law properties. Our result may have impact on future protocol evaluations and designs.

  • J. Chen and Lj. Trajkovic, ''Analysis of Internet topology data,'' Proc. IEEE Int. Symp. Circuits and Systems, Vancouver, British Columbia, Canada, May 2004, vol. IV, pp. 629-632.
  • Hao (Johnson) Chen's M. Sc. thesis: "Analysis of Internet topology data," April 2004.

    Understanding network customers' behavior from billing traces
    Dr. Luc A. Andriantiatsaholiniaina (Postdoctoral fellow) and Dr. Ljiljana Trajkovic (supervisor)

    Collection of user statistics and network traffic is crucial for understanding user behavior and for creating network workload models. It is also valuable for the management of commercial wireless networks. In this project, we report on the analysis of billing records collected from the Telus Mobility Cellular Digital Packet Data (CDPD) network. The longest continuous billing record that we examined covered approximately twenty one days, spanning the Christmas and New Year holiday seasons. We used various tools to graphically illustrate the billing data. We observed that network activities exhibit daily and weekly cycles. Analysis of billing record provided useful information about the usage of an operational wireless network.

    The clustering analysis revealed that customers, as well as network cells, might be classified into few distinct behavioral classes. The clustering analysis using k-means algorithm (available in S-PLUS) revealed four distinct behavioral classes of customers and three classes of network cells as the best results. However, AutoClass clustering method provided thirty two distinct behavioral classes of customers and four classes of network cells. AutoClass proved to be a good tool for clustering small data sets, such as network cells database, which is composed of 60 cells and 5 attributes or the INDEX project database with 84 people and 29 attributes, but it is not suitable for clustering large data set such as customers behavior database with 2096 customers and 8 attributes.

  • L. A. Andriantiatsaholiniaina and Lj. Trajkovic, ''Analysis of user behavior from billing records of a CDPD wireless network,'' Workshop on Wireless Local Networks (WLN) 2002, Tampa, FL, Nov. 2002, pp. 781-790.
  • H. Zhang, L. Andriantiatsaholiniaina, M. Nikolic, S. Petrovic, and Lj. Trajkovic, ''Understanding network traffic from billing traces: customers' behavior analysis,'' The ASI Exchange, Vancouver, BC, Canada, March 2002.

    Using AutoClass for exploring demographic structure of Internet users
    Milan Nikolic (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    The objective of this project was to use an automatic classification program (AutoClass) to extract useful information from the INDEX project (UC Berkeley) database in order to explore the demographic structure of Internet users. AutoClass is an unsupervised Bayesian classification system that seeks a maximum posterior probability classification. The database that we analyzed consisted of 84 cases with 23 attributes. AutoClass found a classification with three classes.

  • First class, with 47 cases (class members), consists of students and technicians, in their 20's or 30's, with a low or mid income.
  • Second class, with 28 cases, consists of professors and a few technicians and administrators in their 30's or 50's, for whom the ''university pays for Internet usage at home,'' and with a high or mid income.
  • Third class, with 9 cases, consists of employees for whom the ''employer pays for Internet usage at home'' and the ''employer pays for Internet usage at work,'' and who have a high or mid income. Our results show that the attributes ''age,'' ''profession,'' ''income,'' and ''who pays for the Internet connection'' were the most influential in making the classification.

  • M. Nikolic and Lj. Trajkovic, ''Clustering analysis of INDEX demographic database using AutoClass,'' The ASI Exchange, Vancouver, BC, Canada, March 2000.

    Control of Communication Networks

    Virtual network embedding for switch-centric and server-centric data center networks
    Ana Laura Gonzalez Rios (M. A. Sc. student), Kamila Bekshentayeva (M. A. Sc. student), Hardeep Kaur Takhar (M. A. Sc. student), and Ljiljana Trajkovic (supervisor)

    Advances in software defined and data center networks (DCNs) have enabled network virtualization that enhances network performance and maximizes profits of Internet service providers. Virtual network embedding (VNE) increases resources utilization and reduces cost of network deployment. Its performance depends on embedding algorithms and data center network topologies. In this project, we evaluate performance of virtual network embedding algorithms based on acceptance ratio, revenue to cost ratio, and node and link utilizations by simulating virtual network embeddings on switch-centric (Spine-Leaf, Three-Tier, Collapsed Core) and server-centric (DCell) data center network topologies. Simulations are performed using the publicly available VNE simulator VNE-Sim. Employed DCN topologies have been implemented using the Fast Network Simulator Setup (FNSS) library.

  • Paper: A. L. Gonzalez Rios, K. Bekshentayeva, M. Singh, S. Haeri, and Lj. Trajkovic, "Virtual network embedding for switch-centric data center networks," in Proc. IEEE Int. Symp. Circuits and Systems, Daegu, Korea, May 2021 (virtual).
  • Presentation: A. L. Gonzalez Rios, K. Bekshentayeva, M. Singh, S. Haeri, and Lj. Trajkovic, "Virtual network embedding for switch-centric data center networks," IEEE Int. Symp. Circuits and Systems, Daegu, Korea, May 2021 (presentation video) (virtual).

    • Comparison of virtualization algorithms and topologies for data center networks
    Hanene Ben Yedder (Ph.D. student), Qingye Ding (Ph.D. stundent), Umme Zakia (Ph.D. student), Zhida Li (Ph.D. student), Dr. Soroush Haeri, and Dr. Ljiljana Trajkovic (supervisor)

    Data centers are core infrastructure of cloud computing. Network virtualization in these centers is a promising solution that enables coexistence of multiple virtual networks on a shared infrastructure. It offers flexible management, lower implementation cost, higher network scalability, increased resource utilization, and improved energy efficiency. In this paper, we consider switch-centric data center network topologies and evaluate their use for network virtualization by comparing Deterministic (D-ViNE) and Randomized (R-ViNE) Virtual Network Embedding, Global Resource Capacity (GRC), and Global Resource Capacity-Multicommodity (GRC-M) Flow algorithms.

  • Paper: H. Ben Yedder, Q. Ding, U. Zakia, Z. Li, S. Haeri, and Lj. Trajkovic, "Comparison of virtualization algorithms and topologies for data center networks," The 26th International Conference on Computer Communications and Networks (ICCCN 2017), 2nd Workshop on Network Security Analytics and Automation (NSAA), Vancouver, Canada, Aug. 2017.
  • Presentaton: H. Ben Yedder, Q. Ding, U. Zakia, Z. Li, S. Haeri, and Lj. Trajkovic, "Comparison of virtualization algorithms and topologies for data center networks," The 26th International Conference on Computer Communications and Networks (ICCCN 2017), 2nd Workshop on Network Security Analytics and Automation (NSAA), Vancouver, Canada, Aug. 2017.
  • Paper: S. Haeri and Lj. Trajkovic, "Virtual network embeddings in data center networks," in Proc. IEEE Int. Symp. Circuits and Systems, Montreal, Canada, May 2016, pp. 874-877.
  • Presentaton: S. Haeri and Lj. Trajkovic, "Virtual network embeddings in data center networks," in Proc. IEEE Int. Symp. Circuits and Systems, Montreal, Canada, May 2016, pp. 874-877.

    • Global resource capacity algorithm with path splitting for virtual network embedding
    Soroush Haeri (Ph.D. student), Qingye Ding (Ph.D. stundent), Zhida Li (Ph.D. student), and Dr. Ljiljana Trajkovic (supervisor)

    Network virtualization enables support and deployment of new services and applications that the current Internet architecture is unable to support. Virtual Network Embedding (VNE) problem that addresses efficient mapping of virtual network elements onto a physical infrastructure (substrate network) is one of the main challenges in network virtualization. The Global Resource Capacity (GRC) is a VNE algorithm that utilizes for virtual link mapping a modified version of Dijkstra's shortest path algorithm. In this paper, we propose the GRC-M algorithm that utilizes the Multicommodity Flow (MCF) algorithm. MCF enables path splitting and yields to higher substrate resource utilizations. Simulation results show that MCF significantly enhances performance of the GRC algorithm.

  • Paper: S. Haeri, Q. Ding, Z. Li, and Lj. Trajkovic, "Global resource capacity algorithm with path splitting for virtual network embedding," in Proc. IEEE Int. Symp. Circuits and Systems, Montreal, Canada, May 2016, pp. 666-669.
  • Poster: S. Haeri, Q. Ding, Z. Li, and Lj. Trajkovic, "Global resource capacity algorithm with path splitting for virtual network embedding," in Proc. IEEE Int. Symp. Circuits and Systems, Montreal, Canada, May 2016, pp. 666-669.

    • Network virtualization and intelligent virtual network embedding
    Soroush Haeri (Ph. D. student) and Dr. Ljiljana Trajkovic (supervisor)

    Network virtualization enables coexistence of multiple virtual networks on a shared infrastructure without requiring unified protocols, applications, and control and management planes. Recent approaches such as Software Defined Networking have enabled cloud service providers to offer virtualized network services that require embedding virtual network requests in data centers. In this project, we employ various algorithms to perform a series of virtual network embeddings on BCube and Fat-Tree substrate networks. We compare these two data center network topologies to determine the topology that is better suited for virtual network embeddings. Furthermore, we formalize the Virtual Node Mapping (VNoM) problem by using the Markov Decision Process (MDP) framework and devise action policies (node mappings) by finding near optimal solutions for the proposed MDP.

  • Paper: S. Haeri and Lj. Trajkovic, "Virtual network embedding via Monte-Carlo tree search," IEEE Transactions on Cybernetics, vol. 48, no. 2, pp. 510-521, Feb. 2018.
  • Paper: S. Haeri and Lj. Trajkovic, "VNE-Sim: a virtual network embedding simulator," in Proc. SIMUTOOLS, Prague, Czech Republic, Aug. 2016.
  • Presentation: S. Haeri and Lj. Trajkovic, "VNE-Sim: a virtual network embedding simulator," SIMUTOOLS, Prague, Czech Republic, Aug. 2016.
  • Sororush Haeri's Ph.D. dissertation: "Applications of reinforcement learning to routing and virtualization in computer networks," and presentation slides, March 2016.

    • Using resource public key infrastructure for secure Border Gateway Protocol
    Majid Arianezhad (Ph. D. student), George Chang (B.Sc. student), and Dr. Ljiljana Trajkovic (supervisor)

    Border Gateway Protocol has been used as the Internet routing protocol for more than a decade. Several security improvements have been introduced and implemented to prevent attacks and address routing instabilities over the years. Yet, BGP is still vulnerable to a variety of attacks due to its lack of integrity and authentication of BGP messages. The proper operation of BGP strongly depends on the security of BGP, based on the observation that any attack on BGP will have an adverse influence on the routing functionality. Given the importance of BGP security, several approaches have been developed to enhance security of BGP sessions.

    In this project, we described the current methods of securing BGP and addressed the present vulnerabilities of the Internet routing system, methods of attacks, and their consequences. We also explored the Resource Public Key Infrastructure, (RPKI), a specialized public-key infrastructure (PKI) developed to help secure the Internet routing. We built a local testbed and showed how RPKI BGP route validation helps to protect the Internet against hijacking routes and mistakenly advertising router. The testbed enabled analyzing the performance and evaluating the security measures of the RPKI route validation mechanism.

  • Paper: G. Chang, M. Arianezhad, and Lj. Trajkovic, "Using resource public key infrastructure for secure border gateway protocol," in Proc. The 29th Annual IEEE Canadian Conference on Electrical and Computer Engineering (CCECE 2016), Vancouver, Canada, May 2016, pp. 381-386.
  • Presentation: G. Chang, M. Arianezhad, and Lj. Trajkovic, "Using resource public key infrastructure for secure border gateway protocol," The 29th Annual IEEE Canadian Conference on Electrical and Computer Engineering (CCECE 2016), Vancouver, Canada, May 2016, pp. 381-386.

    • Diagnostics for BGP routing
    Soroush Haeri (Ph. D. student), Nabil Seddigh (Solana Networks), Bis Nandy (Solana Networks), and Dr. Ljiljana Trajkovic (supervisor)

    Border Gateway Protocol (BGP) is the de facto inter-domain routing protocol in the Internet. Detecting misconfigurations, attacks and link failures are the major concerns related to BGP routing. Various approaches have been proposed in past decade to detect routing anomalies using BGP update messages.

    In this project, we address detection of link-failure events using BGP update messages. Statistical and machine learning-based techniques may be employed to detect the prefixes and autonomous systems that experience link failure. We also surveyed various types of BGP anomalies and proposed detection algorithms.

    Locator/ID separation protocol for BCNET services
    Soroush Haeri (Ph. D. student), Marilyn Hay (BCNET), Toby Wong (BCNET), and Dr. Ljiljana Trajkovic (supervisor)

    The size of the border gateway protocol (BGP) routing tables continues to increase in the default free zone (DFZ), which is a group of the Internet autonomous systems (AS). The ASes in the DFZ do not require a default path to route a packet to the destination. The increase in size of routing table leads to increase in the number of messages exchanged in the network and reduces the network scalability. Both industry and research community are examining the Internet routing architecture in order to provide solutions to these concerns. Furthermore, the existing Internet architecture does not fully support the network mobility since the IP addresses define both location and identity. The Routing Research Group (RRG) of the Internet Research Task Force (IRTF) widely agrees on the separation of the locator and the identity. This separation may enhance the network scalability, traffic engineering, mobility, multi-homing, and network flexibility.

    In this project, we deployed a multi-homed network using the locator ID/separation protocol (LISP) and evaluated LISP's performance.

  • Paper: S. Haeri, R. Gill, M. Hay, T. Wong, and Lj. Trajkovic, "Multihoming with Locator/ID Separation Protocol: an experimental testbed," in Proc. The 7th IEEE/IFIP International Workshop on Management of the Future Internet, Ottawa, ON, Canada, May 2015, pp. 1238-1241.
  • Poster: S. Haeri, R. Gill, M. Hay, T. Wong, and Lj. Trajkovic, "Multihoming with Locator/ID Separation Protocol: an experimental testbed," The 7th IEEE/IFIP International Workshop on Management of the Future Internet, Ottawa, ON, Canada, May 2015, pp. 1238-1241.

    • Intelligent deflection routing protocol for optical burst switched networks
    Soroush Haeri (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Contention is the main source of burst loss in optical burst switched (OBS) networks. Deflection routing is one of the methods to resolve such contention. It requires enhancements only in the routing software without additional hardware installations. Its main goal is to successfully deflect a burst based only on a limited knowledge that nodes possess about their environment.

    The goal of this project is to design an intelligent deflection protocol by enhancing network nodes with decision making algorithms. The protocol enables a node to adapt itself to changes in network topology and traffic patterns.

  • S. Haeri and Lj. Trajkovic, "Deflection routing in complex networks," in Complex Systems and Networks, J. Lu, X. Yu, G. Chen, and W. Yu, Eds., Berlin: Springer, pp. 395-422, 2015.
  • S. Haeri and Lj. Trajkovic, "Intelligent deflection routing in buffer-less networks," IEEE Transactions on Cybernetics, vol. 45, no. 2, pp. 316-327, Feb. 2015.
  • S. Haeri and Lj. Trajkovic, "Deflection routing in complex networks," in Proc. IEEE Int. Symp. Circuits and Systems, Melbourne, Australia, June 2014, pp. 2217-2220.
  • S. Haeri, M. Arianezhad, and Lj. Trajkovic, "A predictive Q-learning-based algorithm for deflection routing in buffer-less networks," in Proc. IEEE International Conference on Systems, Man, and Cybernetics (SMC 2013), Manchester, UK, Oct. 2013, pp. 764-769.
  • S. Haeri, W. W.-K. Thong, G. Chen, and Lj. Trajkovic, "A reinforcement learning-based algorithm for deflection routing in optical burst-switched networks," in Proc. The 14th IEEE International Conference on Information Reuse and Integration, (IRI 2013), San Francisco, Aug. 2013, pp. 474-481.

    • Probabilistic verification of BGP convergence
    Soroush Haeri (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Formal verification of the Border Gateway Protocol specification validates whether or not a specific set of requirements is satisfied. In recent years, the probabilistic behavior of BGP has been explored. Hence, the verification of BGP may also be probabilistic in nature due to its randomized behavior.

    The goal of this project is to design a probabilistic model checking approach to analyze BGP convergence properties that may be employed to automate the BGP convergence analysis.

  • S. Haeri, D. Kresic, and Lj. Trajkovic, "Probabilistic verification of BGP convergence," in Proc. IEEE International Conference on Network Protocols, ICNP 2011, Vancouver, BC, Canada, Oct. 2011, pp. 127-128 (students poster session paper).

    • Spectral analysis of Internet topology graphs
    Laxmi Subedi (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    The discovery of power-laws and spectral properties of the Internet topology indicates a complex underlying network infrastructure. Analysis of spectral properties of the Internet topology has been usually based on the normalized Laplacian matrix of graphs capturing Internet structure on the Autonomous System (AS) level. In this paper, we first extend the previous analysis of the Route Views data to include datasets collected from the RIPE project. Spectral analysis of collected data from the RIPE datasets confirms the previously observed existence of power-laws and similar historical trends in the development of the Internet. Presented spectral analysis of both the adjacency matrix and the normalized Laplacian matrix of the associated graphs also reveals new historical trends in the clustering of AS nodes and their connectivity. The connectivity and clustering properties of the Internet topology are further analyzed by examining element values of the corresponding eigenvectors.

  • L. Subedi and Lj. Trajkovic, "Spectral analysis of Internet topology graphs," in Proc. IEEE Int. Symp. Circuits and Systems, Paris, France, June 2010, pp. 1803-1806.
  • Laxmi Subedi's M.A.Sc. thesis: "Power-laws and spectral analysis of the Internet topology" and presentation slides, Apr. 2010.

    • Analysis of Internet topologies: a historical view
    Mohamadreza Najiminaini (Ph.D. student) and Dr. Ljiljana Trajkovic (supervisor)

    Discovering properties of the Internet topology is important for evaluating performance of various network protocols and applications. The discovery of power-laws and the application of spectral analysis to the Internet topology data indicate a complex behavior of the underlying network infrastructure that carries a variety of the Internet applications. In this paper, we present analysis of datasets collected from the Route Views project. The analysis of collected data shows certain historical trends in the development of the Internet topology. While values of various power-laws exponents have not substantially changed over the recent years, spectral analysis of the normalized Laplacian matrix of the associated graphs reveals notable changes in the clustering of Autonomous System (AS) nodes and their connectivity.

  • M. Najiminaini, L. Subedi, and Lj. Trajkovic, "Analysis of Internet topologies: a historical view," in Proc. IEEE Int. Symp. Circuits and Systems, Taipei, Taiwan, May 2009, pp. 1697-1700.

    • Modeling of TCP with active queue management schemes
    Dr. Judy Liu (Postdoctoral fellow) and Dr. Ljiljana Trajkovic (supervisor)

    The objective of this project is to model TCP mixed with active queue management (AQM) in order to understand and predict the dynamic behavior of packet networks. From the viewpoint of control theory, the network can be regarded as a complex control system. TCP adjusts its sending rate depending on whether or not it has detected a packet loss. Hence, it is natural to model the network system as a discrete model. We plan to model this process as a 'stroboscopic map' where the instant of observation is approximately one RTT. We are currently working on identifying the independent state variables, finding the mathematical relationships among them, and verifying them using ns-2 simulations.

    The basic idea of RED (Random Early Detection) is to sense impending congestion before it happens, and to provide feedback to senders by either dropping or marking packets. The drop probability of RED can be seen as the control law of the network system. Its discontinuity is the main reason behind the occurrence of oscillations and chaos in the system. If the network can be modeled as a second order system, various bifurcation phenomena, such as period-doubling, border-collision (also named as C-bifurcation), saddle-node, Hopf and torus bifurcation, should be observable for various system parameters. We intend to study the nonlinear phenomena in the network by employing bifurcation and chaos theory. We plan to use bifurcation diagrams, strange attractors in phase plane, and the Largest Lyapunov Exponents (LLE) to investigate these phenomena.

  • M. Liu, A. Marciello, M. di Bernardo, and Lj. Trajkovic, ''Discontinuity-induced bifurcations in TCP/RED communication algorithms,'' Proc. IEEE Int. Symp. Circuits and Systems, Kos, Greece, May 2006, pp. 2629-2632.
  • H. Zhang, M. Liu, V. Vukadinovic, and Lj. Trajkovic, ''Modeling TCP/RED: a dynamical approach,'' Complex Dynamics in Communication Networks, Springer Verlag, Series: Understanding Complex Systems, 2005, pp. 251-278.
  • M. Liu, H. Zhang, and Lj. Trajkovic, ''Stroboscopic model and bifurcations in TCP/RED,'' Proc. IEEE Int. Symp. Circuits and Systems, Kobe, Japan, May 2005, pp. 2060-2063.
    Characterization of a simple communication network using Legendre transform
    Takashi Hisakado (Professor, Kyoto University), Vladimir Vukadinovic (M. Sc. student, University of Belgrade) and Dr. Ljiljana Trajkovic (supervisor)

    We describe an application of the Legendre transform to communication networks. The Legendre transform applied to max-plus algebra linear systems corresponds to the Fourier transform applied to conventional linear systems. Hence, it is a powerful tool that can be applied to max-plus linear systems and their identification. Linear max-plus algebra has been already used to describe simple data communication networks. We first extend the Legendre transform as the slope transform to non-concave/non-convex functions. We then use it to analyze a simple communication network. We also propose an identification method for its transfer characteristic, and we confirm the results using the ns-2 network simulator.

  • T. Hisakado, K. Okumura, V. Vukadinovic, and Lj. Trajkovic, ''Characterization of a simple communication network using Legendre transform,'' (invited session) Proc. IEEE Int. Symp. Circuits and Systems, Bangkok, Thailand, May 2003, vol. III, pp. 738-741.
    Delay and throughput differentiation mechanism for non-elevated services
    Vladimir Vukadinovic (M. Sc. student, University of Belgrade) and Dr. Ljiljana Trajkovic (supervisor)

    Internet is a transport infrastructure for applications with various service requirements. However, Internet remains to be a best-effort network without widely deployed mechanisms for service differentiation and quality of service provisioning. Research efforts to provide service differentiation in the Internet have been recently directed toward non-elevated mechanisms. Majority of proposed non-elevated mechanisms rely on the idea of providing low delay service at the expense of increased loss probability. However, these proposals do not consider the influence of delay and loss differentiation on the behavior of TCP, the most widely used transport protocol in today's Internet. Service differentiation mechanisms cannot be designed without taking into account the complexity of TCP's congestion control algorithm.

    Goal of this project is to design a new non-elevated service differentiation mechanism that would provide low-delay service to real-time applications and at least the same throughput to throughput sensitive applications as they would receive in a best-effort network. The new mechanism will include two building blocks: a scheduler for proportional delay differentiation and a controller that will ensure that performance of TCP applications will not be degraded by the presence of the low-delay traffic.Necessary conditions to provide desired service differentiation will be derived by considering delay differentiation algorithm and TCP's congestion avoidance algorithm as a feedback control system. We plan to use the ns-2 simulator to test the new mechanism with existing ns-2 traffic models (CBR, Pareto ON/OFF, and Exponential ON/OFF) and protocols (UDP and TCP NewReno).

  • V. Vukadinovic. G. Petrovic, and Lj. Trajkovic, ''BPR+: a packet scheduling algorithm for proportional delay differentiation,'' YU INFO, Mar. 2004, Kopaonik, Serbia and Montenegro.
  • V. Vukadinovic and Lj. Trajkovic,''RED with dynamic thresholds for improved fairness,'' 2004 ACM Symposium On Applied Computing, SAC '04, Nicosia, Cyprus, Mar. 2004, pp. 371-372.
  • Vladimir Vukadinovic' M. Sc. thesis: ''TCP-friendly packet loss controller for proportional delay differentiation'' and presentation slides, Oct. 2004 (in Serbian).

    Simulation of loss patterns in video transfers over UDP and TCP
    Velibor Markovski (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    We are investigating the patterns of consecutive packet losses (called loss episodes or loss bursts), and the loss behavior in video transfers over UDP and TCP. We consider the impact of loss behavior on high-quality video transfers with stringent end-to-end delay requirements (5 - 30 milliseconds). These requirements imply small maximum queuing delay for the packets in the buffers of the routers. This, in turn, implies that these buffers should be small, which increases the probability of loss and the lengths of the loss episodes.

    We use ns-2 network simulator and genuine traffic traces to obtain the packet loss data and to observe packet loss patterns. We simulate both per-flow loss of a video connection and the aggregate loss at a buffer of a router. We experiment with a variety of simulation scenarios and we consider simple and complex network topologies, User Datagram (UDP) and Transmission Control (TCP) Protocols, various router buffer sizes and utilization levels, and a choice of queue management techniques (Droptail).

    Our simulation results provide a quantitative measure of how the length of these loss episodes increases with the increase of the average utilization levels. They show that lengthy loss episodes contribute significantly to the overall loss patterns, and that under fixed average utilization and during the times of higher congestion, longer loss episodes and shorter loss episode distances occur.

  • V. Markovski and Lj. Trajkovic, ''Analysis of loss periods for video transfers over UDP,'' Proc. SPECTS '2K, Vancouver, BC, Canada, July 2000, pp. 278-285.
  • V. Markovski,''Traffic management using packet scheduling,'' The ASI Exchange, Vancouver, BC, Canada, March 1999.
  • V. Markovski and Lj. Trajkovic, ''Traffic modeling in the TeleLearning environment''(abstract and poster), The Third Annual Conference of the TeleLearning Network of Centres of Excellence, Vancouver, BC, Canada, November 1998.
  • Velibor Markovski's M. A. Sc. thesis: ''Simulation and analysis of loss in IP networks'' and presentation slides, Oct. 2000.

    Analysis and simulation of wireless data network traffic
    Michael Jiang (M. A. Sc. student) and Dr. Stephen Hardy and Dr. Ljiljana Trajkovic (co-supervisors)

    We investigated the impact of traffic patterns on wireless data networks. By performing simulations driven by genuine traffic traces, we evaluated the performance of wireless Cellular Digital Packet Data (CDPD) networks. OPNET network simulation tool was used to simulate the CDPD network of a local commercial service provider (Telus Mobility). In our simulations, we used traffic traces collected from the Telus Mobility network. Statistical analysis of these traces revealed that they exhibit long-range dependent behavior. Our simulation results indicated that they produce longer queues and, thus require larger buffers in the deployed network's switching elements.

  • M. Jiang, M. Nikolic, S. Hardy, and Lj. Trajkovic, ''Impact of self-similarity on wireless network performance,'' Proc. ICC 2001, Helsinki, Finland, June 2001, pp. 477-481.
  • M. Jiang, S. Hardy, and Lj. Trajkovic, ''Simulating CDPD network using OPNET,'' OPNETWORK 2000, Washington, DC, Aug. 2000.
  • C. Cheng, M. Jiang, E. Lo, R. H. S. Hardy, and Lj. Trajkovic, ''OPNET in an education environment: the Simon Fraser University experience,'' OPNETWORK '99, Washington, DC, Aug. 1999.
  • M. Jiang and N. Alborz, ''Modeling wireless data networks,'' The ASI Exchange, Vancouver, BC, Canada, March 2000.
  • M. Jiang,''Wireless data network traffic,'' The ASI Exchange, Vancouver, BC, Canada, March 1999.
  • Michael Jiang's M. A. Sc. thesis: ''Analysis of wireless data network traffic'' and presentation slides, April 2000.

    Simulation of Network Protocols and Algorithms

    Performance evaluation of Border Gateway Protocol with route flap damping and routing policies
    Ravinder Paul (M. A. Sc. student) and Ljiljana Trajkovic (supervisor)

    Route flap damping (RFD) is the occurrence where routers exchange repeated withdrawals and re-announcements of routes. RFD may cause instability of the Internet routing system. Several algorithms were proposed to address the issue of route flapping. However, because of aggressiveness of the RFD algorithms in suppressing routes, they are not widely used in the Internet. In this project, we address the issue of aggressiveness of the RFD algorithms by proposing to change value of the RFD parameter called maximum suppress value. RFD and BGP routing policies play a significant role in preserving the Internet routing stability and BGP convergence time. In this thesis, we also evaluate the impact of routing policies on BGP convergence time and the number of route flaps.

  • R. Gill, R. Paul, and Lj. Trajkovic, "Effect of MRAI timers and routing policies on BGP convergence times," in Proc. 31st IEEE Int. Performance, Computing, and Communications Conference, Austin, TX, USA, Dec. 2012, pp. 314-323.

    • Effect of MRAI timers on BGP convergence times
    Rajvir Gill (M. A. Sc. student) and Ljiljana Trajkovic (supervisor)

    The Border Gateway Protocol (BGP) is an Inter-Autonomous System (AS) routing protocol currently used in the Internet. The Minimal Route Advertisement Interval (MRAI) plays a prominent role in convergence of the BGP. The previous studies have suggested using the adaptive MRAI and reusable timers to reduce the BGP convergence time. The adaptive MRAI timers perform well under the normal load of BGP update messages. However, a large number of BGP update messages may flood the Internet routers.In this thesis, we propose a new algorithm called MRAI with Flexible Load Dispersing (FLD-MRAI) that reduces the router's overhead by dispersing the load in case of a large number of BGP update messages. We examine the MRAI timers under both the normal and heavy loads of BGP update messages. The proposed algorithm is evaluated using the ns-BGP network simulator. Network topologies are derived from the BCNET BGP traffic and generated using various topology generators.

  • R. Gill, R. Paul, and Lj. Trajkovic, "Effect of MRAI timers and routing policies on BGP convergence times," in Proc. 31st IEEE Int. Performance, Computing, and Communications Conference, Austin, TX, USA, Dec. 2012, pp. 314-323.

    • Improving BGP convergence using route flap damping algorithms
    Ravinder Paul (M. A. Sc. student) and Ljiljana Trajkovic (supervisor)

    Route flap damping (RFD) is the phenomenon where routers exchange repeated withdrawal and re-announcement of routes. RFD may cause instability of the Internet routing system. Several algorithms were proposed to address the issue of route flapping. In this project, we plan to implement routing polices in the ns-BGP network simulator and evaluate effect of routing policies on RFD.

  • Route Flap Damping and Adaptive Minimal Route Advertisement Interval in ns-BGP 2.0 was revised by Rajvir Gill and Ravinder Paul.
  • Route Flap Damping and Adaptive Minimal Route Advertisement Interval in ns-BGP 2.0 (developed by W. Shen and N. Laskovic) algorithms are implemented in ns-2 using ns-BGP 2.0 module (developed by T. D. Feng).

    Improving BGP convergence time using MRAI timers
    Rajvir Gill (M. A. Sc. student) and Ljiljana Trajkovic (supervisor)

    The interval of the Minimal Route Advertisement Interval (MRAI) plays an important role on the Border Gateway Protocol (BGP) convergence time. Previous studies have suggested using adaptive MRAI and reusable timers to reduce convergence time of BGP. However, the adaptive MRAI algorithm works for routers under normal load of BGP updates. Currently, large number of BGP updates may flood Internet routers. We plan to reduce the router's overhead of processing a large number of BGP updates and examine the MRAI timers under heavy BGP updates load. The proposed algorithm will be evaluated using the ns-BGP network simulator and topologies derived from the BCNET BGP traffic.

  • Route Flap Damping and Adaptive Minimal Route Advertisement Interval in ns-BGP 2.0 was revised by Rajvir Gill and Ravinder Paul.
  • Route Flap Damping and Adaptive Minimal Route Advertisement Interval in ns-BGP 2.0 (developed by W. Shen and N. Laskovic) algorithms are implemented in ns-2 using ns-BGP 2.0 module (developed by T. D. Feng).

    Streaming video and audio content over mobile WiMAX networks
    Will Hrudey and Ljiljana Trajkovic

    WiMAX (Worldwide Interoperability for Microwave Access) embodies the IEEE 802.16 family of standards that provision wireless broadband access. With the IEEE 802.16e-2005 mobility amendment, WiMAX promises to address the ever-increasing demand of mobile high-speed wireless data in fourth generation (4G) networks. WiMAX market studies continue to project increased subscriber growth rates and planned carrier trials worldwide. With these projected growth rates, in order to understand if WiMAX is a formidable player in 4th generation mobile systems, it is desirable to quantify performance using video-rich emerging services to sufficiently load and stress the network to exploit the potential bandwidth, delay and mobility limitations. Accordingly, the goal of this project is to enhance an existing OPNET simulation model to simulate video content representative of IPTV and other video-rich emerging services to adequately load and analyze the Mobile WiMAX technology.

  • W. Hrudey and Lj. Trajkovic, "Mobile WiMAX MAC and PHY layer optimization for IPTV," Special issue on Recent Advances in Simulation and Mathematical Modeling of Wireless Networks, Mathematical and Computer Modelling, Elsevier, vol. 53, pp. 2119-2135, Mar. 2011.

    • Streaming video content over WiMAX and ADSL access networks
    Will Hrudey and Ljiljana Trajkovic

    Worldwide Interoperability for Microwave Access (WiMAX) embodies the IEEE 802.16 family of standards that provide wireless broadband access to residential and commercial Internet subscribers. While other WiMAX applications exist, there is an increasing trend to employ WiMAX for last-mile Internet access to circumvent the high deployments costs and local loop distance limitations associated with wired Asymmetric Digital Subscriber Line (ADSL) connections. We use the OPNET Modeler to simulate bandwidth intensive, delay sensitive, video traffic representative of Internet Protocol Television (IPTV) and other video-rich applications over WiMAX and ADSL. These video streams are typically encoded using MPEG-x codecs. Although marginally loss-tolerant, performance of these streams is inherently a function of available bandwidth, buffering, and delay characteristics of the underlying network. Hence, in this paper, we examine four performance factors while streaming two hours of video content to client subscribers to determine whether WiMAX can deliver access network performance comparable to ADSL for video applications.

  • W. Hrudey and Lj. Trajkovic, "Streaming video content over IEEE 802.16/WiMAX broadband access," OPNETWORK 2008, Washington, DC, Aug. 2008.

    • Integrating ns-BGP with the ns-2.34 network simulator
    Reza Sahraei and Ljiljana Trajkovic

    The Border Gateway Protocol, BGP, is a de facto inter-Autonomous Systems (ASs) routing protocol. The primary function of a BGP speaking system is to exchange network reachability information with other BGP systems. It was formally proposed in Request For Comments (RFC) 1771 by the network working group within the Internet Engineering Task Force (IETF). The Internet has a very dynamic nature and this has an effect on the performance of the routing protocols such as BGP. Therefore, ns-BGP was developed for the ns-2 network simulator by importing the code from BGP implementation in SSFNET and converting them to C++ and OTcl code in 2003. Later, the ns-BGP upgraded to be compatible with the latest version of ns, which was ns-2.33 in 2008. This project integrates ns-BGP for the latest stable ns release ns-2.34.

  • The ns-2.34-BGP implementation was based on the ns-2.27-BGP module (developed by T. D. Feng) and ns-2.33-BGP (developed by W. Hrudey): Integrating ns-BGP with the ns-2.34 network simulator (developed by R. Sahraei).
  • Integrating ns-BGP with the ns-2.34 network simulator was revised by Rajvir Gill and Ravinder Paul.

    Integrating ns-BGP with the ns-2.33 network simulator
    Will Hrudey and Ljiljana Trajkovic

    The border gateway protocol (BGP) is an inter-Autonomous System (AS) routing protocol utilized as the core routing protocol in the Internet today. It was formally proposed in Request For Comments (RFC) 1771 by the network working group within the Internet Engineering Task Force (IETF). Primarily, BGP exchanges network reachability information with other BGP systems. Since BGP performance is affected by the dynamic nature of the Internet, ns-BGP was developed for the ns-2 network simulator in 2003 to facilitate realistic, flexible BGP routing experimentation.

    In parallel with the ns-BGP development, academic and research communities continued to develop ns-2. Consequently, this led to an incompatible ns-BGP module with current versions of the simulator. Therefore, in an effort to aid further BGP research efforts, this project will integrate ns-BGP with the latest stable version of the simulator thereby benefitting from core ns-2 feature enhancements and maintenance updates over the past five years.

  • The ns-2.33 BGP implementation was based on the ns-BGP 2.0 module (developed by T. D. Feng): Integrating ns-BGP with the ns-2.33 network simulator (developed by W. Hrudey).

    TCP with adaptive delay and loss response for heterogeneous networks
    Modupe Omueti and Ljiljana Trajkovic

    Long propagation delays and high bit error rates in heterogeneous networks with geostationary earth orbit (GEO) satellite links have negative impact on the performance of Transmission Control Protocol (TCP). In this paper, we propose modifications to TCP by introducing adaptive delay and loss response (TCP-ADaLR) to mitigate the adverse effects of satellite link characteristics. The proposed modifications incorporate delayed acknowledgment (ACK) recommended for Internet hosts. TCP-ADaLR introduces adaptive window increase and loss recovery mechanisms to address TCP performance degradation in satellite networks. We evaluate and compare the performance of TCP-ADaLR, TCP SACK, and TCP NewReno, with delayed ACK enabled and disabled. In the absence of losses, TCP-ADaLR exhibits the shortest user-perceived latency for HTTP and FTP applications. In the presence of only congestion losses, TCP-ADaLR shows comparable performance to TCP SACK and TCP NewReno. In the presence of only error losses, TCP-ADaLR exhibits improvements up to 61% and 76% in throughput and utilization, respectively. In the presence of both congestion and error losses, TCP-ADaLR exhibits goodput and throughput improvements up to 43%. TCP-ADaLR exhibits the best performance in the absence of losses and in the presence of losses due to both congestion and errors. It is also friendly to TCP NewReno, exhibits better fairness, and maintains TCP end-to-end semantics.

  • M. Omueti and Lj. Trajkovic, ''TCP with adaptive delay and loss response for heterogeneous networks,'' WiCON 2007, Austin, TX, Oct. 2007.
  • M. Omueti and Lj. Trajkovic, ''OPNET model of TCP with adaptive delay and loss response for broadband GEO satellite networks,'' OPNETWORK 2007, Washington, DC, Aug. 2007.

    M-TCP+: Using Disconnection Feedback to Improve Performance of TCP in Wired/Wireless Networks
    Modupe Omueti and Ljiljana Trajkovic

    In this project, we propose the M-TCP+ algorithm for heterogeneous wired/wireless networks. The algorithm is a modification of M-TCP that was proposed for deployment in mobile cellular networks. It is recommended that Internet hosts enable the delayed acknowledgement (delayed ACK) option to maximize network bandwidth by reducing the number of ACKs sent to a TCP sender by a TCP receiver. The M-TCP+ algorithm performs best when the TCP delayed ACK option is enabled. The algorithm relies on feedback sent from a wireless host in anticipation of disconnections. We compare the performance of the M-TCP+ algorithm with the performance of M-TCP, TCP NewReno, and TCP SACK in both the absence and the presence of disconnections for a file transfer protocol (download) application. We also simulate network scenarios with traffic congestion. The M-TCP+ algorithm performance is evaluated in terms of file download response time, goodput, and retransmission ratio with and without the delayed ACK option. In scenarios without disconnections, the M-TCP+ algorithm does not introduce significant processing delay. Furthermore, in scenarios with disconnections, the M-TCP+ algorithm shows 2%-15% performance improvement.

  • M. Omueti and Lj. Trajkovic, ''M-TCP+: using disconnection feedback to improve performance of TCP in wired/wireless networks,'' Proc. SPECTS 2007, San Diego, CA, USA, July 2007, pp. 443-450.

    Improving the Performance of the Gnutella Network
    Andre Dufour (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    We examine the behaviour of the Gnutella peer-to-peer file sharing network and propose a protocol modification intended to improve its performance. Because its overlay topology is not well matched to the underlying physical network, Gnutella exhibits sub-optimal performance in terms of message latency. In order to characterize this performance, we modified an existing Gnutella simulation framework developed for network simulator (ns-2) to gather information about query and query hit propagation. We then modified the protocol implemented in the simulation to use the Vivaldi synthetic coordinate system and to bias neighbour selection to favour nodes that are ''close" in the Euclidian sense. Simulations with the adapted Gnutella protocol showed an improvement in query and query hit propagation times.

  • Gnutaldi simulator (developed by A. Dufour): Improving the Performance of the Gnutella Network.
  • A. Dufour and Lj. Trajkovic, ''Improving Gnutella network performance using synthetic coordinates,'' presented at The Third Int. Conf. on Quality of Service in Heterogeneous Wired/Wireless Networks (QShine 2006), Waterloo, ON, Canada, August 2006.

    BGP route flap damping algorithms
    Wei (Steve) Shen (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Route flap damping (RFD) plays an important role in maintaining the stability of the Internet routing system. It functions by suppressing routes that persistently flap. Several existing algorithms address the issue of identifying and penalizing route flaps. In this project, we compare three such algorithms: original RFD, selective RFD, and RFD+. We implement these algorithms in ns-2 and evaluate their performance. We also propose possible improvements to the RFD+ algorithm.

  • RFD algorithms are implemented in ns-2 using ns-BGP 2.0 module (developed by T. D. Feng): Route Flap Damping and Adaptive Minimal Route Advertisement Interval in ns-BGP 2.0 (developed by W. Shen and N. Laskovic).
  • W. Shen and Lj. Trajkovic ''BGP route flap damping algorithms,'' Proc. SPECTS 2005, Philadelphia, PA, July 2005, pp. 488-495.

    BGP with an adaptive Minimal Route Advertisement Interval
    Nenad Laskovic (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    The duration of the Minimal Route Advertisement Interval (MRAI) and the implementation of MRAI timers have a significant influence on BGP convergence time. Previous studies have reported existence of optimal MRAI values that minimize BGP convergence time for various network topologies. These optimal values depend on network topologies and traffic loads. In this project, we propose using adaptive MRAIs for each destination in BGP speakers. Furthermore, we introduce reusable MRAI timers that independently limit the number of advertisements of various destinations. The proposed modification of BGP is named BGP with adaptive MRAI. We evaluate the new algorithm by introducing a new model for the BGP processing delay. ns-2 simulation results demonstrate that BGP with adaptive MRAI results in a considerably shorter BGP convergence time, with a similar number of update messages compared to the current BGP implementation. Furthermore, BGP convergence time depends linearly on BGP processing delay. For large networks, BGP with adaptive MRAI may reduce BGP convergence time by 80% and the number of update messages by 20%.

  • BGP with adaptive MRAI is implemented in ns-2 using ns-BGP 2.0 module (developed by T. D. Feng): Route Flap Damping and Adaptive Minimal Route Advertisement Interval in ns-BGP 2.0 (developed by W. Shen and N. Laskovic).
  • N. Laskovic and Lj. Trajkovic, "BGP with an adaptive minimal route advertisement interval," Proc. 25th IEEE Int. Performance, Computing, and Communications Conference, Phoenix, AZ, Apr. 2006, pp. 135-142.

    Implementation of BGP in a network simulator
    Tony Feng (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Border Gateway Protocol (BGP) is the inter-domain routing protocol currently employed in Internet. Internet growth imposes increased requirements on BGP performance. Recent studies revealed that performance degradations in BGP are due to the highly dynamic nature of the Internet. Undesirable properties of BGP, such as poor integrity, slow convergence, and divergence, have been reported by the research community. Theoretical analysis and empirical measurements have been employed in the past, albeit with certain limitations. Simulations allow more realistic experiments with fewer simplifications than the theoretical approach and with enhanced flexibility than empirical studies permit.

    In this thesis, we describe the design and implementation of a BGP-4 model (ns-BGP) in the network simulator ns-2 by porting the BGP-4 implementation from SSFNet. The ns-BGP node is based on the existing ns-2 unicast node and the SSF.OS.BGP4 model from SSFNet. In order to provide socket support and at the same time maintain the structure of SSF.OS.BGP4, we also ported to ns-2 TcpSocket, the socket layer implementation of SSFNet. In order to support the IPv4 addressing and packet forwarding, the basic address classifier was replaced with a new address classifier in ns-2 named IPv4Classifier. We also modified FullTcpAgent, the TCP agent used by TcpSocket, to support user data transmission.

    We performed a suit of validation tests to ensure that the ns-BGP model complies with the BGP-4 specifications, including BGP-4 features such as: basic peer session management (keep and drop peer), route selection, reconnection, internal BGP (iBGP), and route reflection. Finally, in the scalability analysis of ns-BGP, we showed that the model scales with respect to the number of peer sessions and size of routing tables.

  • ns-BGP 2.0 (developed by T. D. Feng):
  • T. D. Feng, R. Ballantyne, and Lj. Trajkovic, ''Implementation of BGP in a network simulator,'' Proc. Applied Telecommunication Symposium, ATS '04, Arlington, Virginia, Apr. 2004, pp. 149-154.

    Selective-TCP for wired/wireless networks
    Rajashree Paul (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    One of the main reasons for TCP's degraded performance in wireless networks is TCP's interpretation that packet loss is caused by congestion. However, in wireless networks, packet loss occurs mostly due to high bit error rate, packet corruption, or link failure. TCP performance in wired/wireless networks may be substantially improved if the cause of packet loss could be distinguished and appropriate rectifying measures taken dynamically. We propose a new end-to-end TCP protocol named Selective-TCP, which distinguishes between congestion and wireless link transmission losses (high bit error rate and/or packet corruption). When detecting packet loss, Selective-TCP invokes correction mechanisms. It is suited for mixed wired/wireless networks and shows increase in goodput when compared to TCP NewReno.

  • Selective-TPC (developed by R. Paul): Selective-TCP for Wired/Wireless Networks.
  • R. Paul and Lj. Trajkovic, ''Selective-TCP for wired/wireless networks,'' SPECTS 2006, Calgary, AL, Canada, Aug. 2006, pp. 339-346.

    TCP packet control for wireless networks
    Wan G. Zeng (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    We propose packet control algorithms to be deployed in intermediate network routers. They improve TCP performance in wireless networks with packet delay variations and long sudden packet delays. The ns-2 simulation results show that the proposed algorithms reduce the adverse effect of spurious fast retransmits and timeouts and greatly improve the goodput compared to the performance of TCP Reno. The TCP goodput was improved by ~30% in wireless networks with 1% packet loss. TCP performance was also improved in cases of long sudden delays. These improvements highly depend on the wireless link characteristics.

  • TCP with Packet Control is implemented in ns-2: TCP with Packet Control.
  • W. G. Zeng and Lj. Trajkovic, ''TCP packet control for wireless networks,'' Proc. IEEE Int. Conf. on Wireless and Mobile Computing, Networking and Communications (WiMob 2005), Montreal, Canada, Aug. 2005, pp. 196-203.

    Modeling and performance evaluation of a General Packet Radio Services (GPRS) network using OPNET
    Renju Narayanan (M. A. Sc. student), Modupe Omueti (M. A. Sc. student), and Dr. Ljiljana Trajkovic (supervisor)

    GPRS is a Global System for Mobile Communications (GSM) based packet switched wireless network technology deployed around the world. The main components of a GPRS system are: Mobile Station (MS),Base Station Subsystem (BSS), Serving GPRS Support Node (SGSN), Home Location Register (HLR), and Gateway GPRS Support Node (GGSN).

    In this project, we plan to enhance the current GPRS OPNET model by implementing the Medium Access Control/Radio Link Control (MAC/RLC) layer in the MS and the BSS for contention resolution and the BSS GPRS protocol (BSSGP) in the BSS and the SGSN for exchanging QoS related information. We also plan to evaluate the performance of the GPRS network using the enhanced model.

  • R. Narayanan and Lj. Trajkovic, ''General Packet Radio Service OPNET model,'' OPNETWORK 2006, Washington, DC, Aug. 2006.
  • M. Omueti, R. Narayanan, and Lj. Trajkovic, ''Effect of cell update on performance of General Packet Radio Service,'' OPNETWORK 2006, Washington, DC, Aug. 2006.
  • R. Narayanan, P. Chan, M. Johansson, F. Zimmermann, and Lj. Trajkovic, ''Enhanced General Packet Radio Service OPNET model,'' OPNETWORK 2004, Washington, DC, Aug. 2004.

    Simulation of General Packet Radio Services (GPRS) network system using OPNET
    Ricky Ng (M. Eng. student) and Dr. Ljiljana Trajkovic (supervisor)

    We plan to model the signaling behavior of the SGSN system and create a model using the OPNET simulation tool.

    The Serving General Packet Radio Services Support Node (SGSN) signaling plane model is capable of handling various signaling traffic profiles such as attach, activation, and deactivation. The model can also generate statistics related to the system's performance. We also plan to simulate the user data procedure in order to illustrate various class of GPRS Quality of Service subscribed by Mobile Station (MS) that will lead to different end-to-end delays in the data session. The SGSN model can then be enhanced to incorporate parameters extracted from lab measurements in order to monitor the performance of the real SGSN system. The SGSN model will not only provides a flexible environment to collect a wide range of data, but will also serve as a performance predication and evaluation tool.

  • R. Ng and Lj. Trajkovic, ''Simulation of general packet radio service network,'' OPNETWORK 2002, Washington, DC, Aug. 2002.
  • Ricky Ng's M.Eng. project: ''Simulation of General Packet Radio Service (GPRS) network'' and presentation slides, April 2002.

    Traffic engineering prioritized IP packets over Multi-Protocol Label Switching (MPLS) network
    Danny Yip (M. Eng. student) and Dr. Ljiljana Trajkovic (supervisor)

    The objective of this project is to examine:
    1. Different priorities defined in the Internet Protocol (IP) with emphasis on IPv6, and the importance of traffic engineering based on assigning priorities to packets.
    2. Limitations of Multi-Protocol Label Switching (MPLS) protocol in prioritized IP traffic, and
    3. Enhancement of the protocol so that Internet Serviced Providers (ISP) using MPLS can improve their network utilization when carrying prioritized IP traffic, can provide better Quality of Services (QoS), and can offer more Classes of Services (CoS).

    We used ns-2 to simulate network performance.

  • ns-2 modifications: PBER-LSR_code.zip (code developed by D. Yip and modified by N. Laskovic).
  • Danny Yip's M.Eng. project: ''Traffic engineering prioritized IP packets over MPLS networks'' and presentation slides, March 2002.

    Enhancements and performance evaluation of wireless local area networks
    James (Jiaqing) Song (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Unlike wired networks that can provide large bandwidth, the bandwidth of wireless local area networks (WLANs) is rather limited because they rely on an inexpensive, but error prone, physical medium (air). Hence, it is important to improve their loss performance.

    In this paper, we investigate several methods for improving the performance of WLANs. We survey the current research literature dealing with improving performance on various wireless network layers. We describe OPNET implementations of three approaches: tuning the physical layer related parameters, tuning the IEEE 802.11 parameters, and using an enhanced link layer (media access control) protocol. Finally, we describe several simulation scenarios and present simulation results that demonstrate the effectiveness of the three approaches.

  • J. Song and Lj. Trajkovic, ''Enhancements and performance evaluation of wireless local area networks,'' OPNETWORK 2003, Washington, DC, Aug. 2003.

    Route optimization of mobile IP over IPv4
    Hao (Leo) Chen (M. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    Mobile Internet Protocol has been proposed by IETF to support portable IP addresses for mobile devices that often change their network access points to the Internet. In the basic mobile IP protocol, datagrams sent from wired or wireless hosts and destined for the mobile host that is away from home, have to be routed through the home agent. Nevertheless, datagrams sent from mobile hosts to wired hosts can be routed directly. This asymmetric routing, called ''triangle routing,'' is often far from optimal and ''route optimization'' has been proposed to address this problem. In this paper, we present the implementation of ''route optimization'' extension to mobile IP in the \ns\ simulator. We illustrate simulations of the mobile IP with route optimization with simulation scenarios, parameters, and simulations results.

  • Mobile IP with route optimization: src.tar.gz (code developed by H. Chen).
  • H. Chen and Lj. Trajkovic, ''Route optimization in mobile IP,'' Proc. IEEE Workshop on Wireless Local Networks, WLN 2002, Tampa, FL, Nov. 2002, pp. 847-848.

    Implementation and performance simulation of VirtualClock scheduling algorithm in IP networks
    Nazy Alborz (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    We use OPNET simulation tool to model the VirtualClock scheduling mechanism. The algorithm is implemented in the output buffers of the IP router objects in OPNET. The model is then incorporated in the IP layer of the network layer hierarchy so that it can communicate with upper and lower network layer objects.

    We compared the performance of the VirtualClock algorithm and several other scheduling mechanisms in packet networks, such as Weighted Fair Queuing (WFQ), Custom Queuing (CQ), and Priority Queuing (PQ). The performance was compared in terms of fairness, packet end-to-end delay, and the number of packet loss during various time periods. We also simulated the effect of these algorithms on the performance of several Internet applications, such as HTTP, FTP, IP Telephony, and Video Conferencing.

  • N. Alborz and Lj. Trajkovic, ''Implementation of VirtualClock scheduling algorithm in OPNET,'' OPNETWORK 2001, Washington, DC, Aug. 2001.
  • N. Alborz, M. Keyvani, M. Nikolic, and Lj. Trajkovic, ''Simulation of packet data networks using OPNET,'' OPNETWORK 2000, Washington, DC, Aug. 2000.
  • N. Alborz, Q. Shao, and Lj. Trajkovic, ''Simulation and analysis of the VirtualClock scheduling algorithm,'' The ASI Exchange, Vancouver, BC, Canada, March 2002.
  • N. Alborz, B. Chen, and Lj. Trajkovic, ''Modeling packet scheduling algorithms in IP routers,'' The ASI Exchange, Vancouver, BC, Canada, March 2001.
  • Nazy Alborz's M. A. Sc. thesis: ''Implementation and performance simulation of Virtual Clock scheduling algorithm in IP networks'' and presentation slides, April 2002.

    Simulation of quality of service parameters in IP networks
    Bruce Chen (B. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    The main objective of our research is to simulate the quality of service (QoS) parameters in Internet Protocol (IP) networks with various types of traffic sources. The main QoS parameters of interest are packet loss due to buffer overflow, and packet delay due to queuing in the buffers.

    We use network simulator ns-2 to perform trace driven simulations using simple network topologies. We employ MPEG-1 video traces to generate traffic that was transmitted over the User Datagram Protocol (UDP). Our simulation scenarios are used to investigate how various queuing mechanisms affect the characteristics of the QoS parameters. We simulated FIFO (First In First Out) buffer with a DropTail queue management policy, Random Early Drop (RED), Fair Queuing (FQ), Stochastic Fair Queuing (SFQ), and Deficit Round Robin (DRR) active queue management schemes.

  • Bruce Chen's B.A.Sc. thesis: ''Simulation and analysis of quality of service parameters in IP networks with video traffic'' and presentation slides, December 2001.

    OPNET modeling and simulation of CDPD MAC layer behavior
    Eric Keung (B. A. Sc. student), Savio Lau (B. A. Sc. student), and Dr. Ljiljana Trajkovic (supervisor)

    As part of our undergraduate thesis project, we are working on enhancing the OPNET model of the Cellular Digital Packet Data (CDPD) Medium Access Control (MAC) Layer. The enhancements include handling burst uplink data transmission, competing mobile stations, and collision detection. We use the OPNET model to examine the system's queuing behavior in terms of buffer requirements and packet delays. In addition to various standard traffic source models, such as Poisson, bursty (on-off) and self-similar generators, in our simulations we also employ genuine traffic traces.

    OPNET modeling and simulation of Deficit Round Robin scheduling algorithm for IP networks
    Amir Jodari (B. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    The main objectives of this project is to implement an OPNET model of the Deficit Round Robin scheduling algorithm, and to compare its performance to other scheduling mechanisms in packet networks. Deficit Round Robin enables handling of variable packet sizes, without knowing the average packet size of the flows. The OPNET simulation tool enables modeling of communication networks and distributed systems. It contains tools for design simulation, data collection, and data analysis.

    Various projects

    Co-design of High-Performance Computing Interconnection Networks
    Paul Beaujean (ENSIIE undergraduate student) and Dr. Ljiljana Trajkovic (supervisor)

    Analysis of high-performance computing interconnection networks is necessary to develop power-efficient, low-latency, and throughput-oriented supercomputers. As the future exascale and even zettascale is expected to deal with million, even billion-way, parallelism, there needs to be a formal study of interconnection networks as instruments of computation and not merely communication channels.

    In order to design such supercomputers, high-performance computing interconnection networks have to be studied at a very large scale. The theory of interconnection networks must be expanded upon and then extended to a formal framework, namely a topology-aware model of parallel and distributed computation, taking roots in process calculus and its variations. The products of this theoretical framework must be then assessed in terms of power consumption, manufacturing feasibility, and programmability.

    High-productivity parallel programming languages require an underlying distributed instruction set architecture with inexpensive message passing, synchronisation primitives, horizontal and vertical data movement, and more. All of these features must be designed theoretically and in relation to network topology. In addition, the scale of these computers requires a rethinking of the services offered by the operating system and the run-time system to conform with availability and fault-resilience issues while efficiently utilizing the available computing resources through topology-aware scheduling.

    Performance measurements of multimedia traffic in an IP over ATM local area network
    Milan Nikolic (M. A. Sc. student) and Dr. Ljiljana Trajkovic (supervisor)

    We have built an ATM testbed comprised of two ATM edge switches (Newbridge MainStreet 36150), and two Pentium III workstations connected to the ATM network via Ethernet cards. We used MBone and NetMeeting multimedia-conferencing systems to measure and evaluate performance of audio and video transmissions using both CBR and VBR services in an IP over ATM network. Using Spirent's SmartBits load generator, and in compliance with RFC 2544, we measured and analyzed throughput, packet delay, and delay jitter as main parameters for measuring forwarding performance and quality of service in multimedia applications.

    The ATM Traffic Monitor script, a simple network management graphical user interface written in Tcl, Tk, and Expect scripting languages, provided an easy graphical capture of the aggregate traffic sent through Ethernet cards of the ATM switches. We also used MBone to multicast the Open Forum session at IFSA/NAFIPS 2001 conference, held in Vancouver on July 25-28, 2001. Audio and video signals were sent using MBone tools (running on Windows OS) to the MBone network using DVMRP tunneling through ADSL (Telus) line, via SFU campus network, to BCnet GigaPOP.

  • M. Nikolic, C. Ling, and Lj. Trajkovic, ''Using an ATM testbed for videoconferencing,'' The ASI Exchange, Vancouver, BC, Canada, March 2001.
  • Milan Nikolic's M. A. Sc. thesis: ''Performance measurements of multimedia transmissions in IP over ATM networks'' and presentation slides, December 2002.

    How to evaluate field test performance for a CDMA2000 handset
    Jeffrey Lai (M. Eng. student) and Dr. Ljiljana Trajkovic (supervisor)

    This project deals with the CDMA technology and the added benefits provided by the 3G CDMA2000. We describe the testing methodology within a software engineering model, and differentiate the field test from other testing activities. Field test is an important and high priority task in R&D projects and it is mandatory to include field tests in any handset development project. We elaborate on the details of field test activities, which include test planning, test tools application, test sites selection, test case design, and test results analysis. We also illustrate the typical field test analysis required for R&D field tests. In particular, our field test results confirm that the message flow complies with the IS-2000.5 Upper Layer (L3) Signaling Standard.

  • Jeffrey Lai's M.Eng. project: ''How to evaluate field test performance for a CDMA2000 handset'' and presentation slides, April 2003.

    Convergence behavior of RIP and OSPF network protocols
    Hubert Pun (M. Eng. student) and Dr. Ljiljana Trajkovic (supervisor)

    In this project we investigate the characteristics of Internet Protocol (IP) addressing. We first review the similarities and differences between the Variable Length Subnet Mask (VLSM) and Classless Inter-Domain Routing (CIDR). Moreover, we also consider the advantages of the classless over the classful nature of a routing protocol. We discuss the compositions of routing tables. We examine in details the Routing Information Protocol (RIP) and the Open Shortest Path First (OSPF) routing protocols.

    We performed experiments involving seven Cisco routers. The three cases of interests are:
    - impact of a failure Ethernet link to the OSPF convergence
    - impact of a broken Frame Relay (FR) Virtual Circuit (VC) to the RIP convergence
    - impact of a broken FR VC to the redistribution convergence.

    The RIP's timers are changed in each of these three cases to measure performance improvements.

  • Hubert Pun's M.Eng. project: ''Convergence behavior of RIP and OSPF network protocols'' and presentation slides, December 2001.

    Hardware implementation of a high-speed symmetric crossbar switch
    Maryam Keyvani (M. A. Sc. student), Arash Haidari-Khabbaz (B. A. Sc student), and Dr. Ljiljana Trajkovic and Dr. Stephen Hardy (co-supervisors)

    We are working on a hardware implementation of a crossbar packet switch for high-speed data networks. We use VHDL to describe our design, the ALTERA MAX+PLUS II tools to simulate it, and the FLEX 10KE ALTERA FPGA to implement it on a chip. The switch has 8 input and 8 output ports, with input queuing. The switch is capable of handling fixed sized packets, such as ATM cells.

    The switch architecture consists of input buffers, input port controllers, destination look-up tables, a centralized scheduler, and a crossbar fabric. The packets first arrive (ingress) to the input ports of the switch. There, serial data is shifted into a serial shift register. As soon as a byte of data is received, it is loaded into a FIFO queue. Each input port has a controller that queues the header of each packet in a separate FIFO buffer, extracts address information from the header of the packet, and sends it to a programmable look-up table (LUT). The LUT returns a destination port address. Based on this address, the controller sends a request to the centralized scheduler. The scheduler receives requests from all input ports and grants them based on a simple two-dimensional ripple-carry arbiter architecture called Rectilinear Propagation Arbiter (RPA). A ''round robin'' priority scheme ensures fairness to all the input ports. Once a grant is issued, the crossbar fabric is configured to map the input port that received a grant to its output port destination. The outgoing (egress) packets are stored into another shift register and then shifted serially to the output link.

  • M. Keyvani and Lj. Trajkovic, ''VHDL implementation of a crossbar packet switch," The ASI Exchange, Vancouver, BC, Canada, March 2001.
  • Maryam Keyvani's M. A. Sc. thesis: "Hardware implementation of a high-speed symmetric crossbar switch" and presentation slides, August 2001.
    • ICON DAWN SIMON VARIOUS