International Journal on Foundations of Computer Science & Technology (IJFCST)

ISSN: 1839-7662

https://wireilla.com/ijfcst/index.html

Scope & Topics

International Journal on Foundations of Computer Science & Technology (IJFCST) is a Bi-monthly peer- reviewed and refereed open access journal that publishes articles which contribute new results in all areas of the Foundations of Computer Science & Technology. Over the last decade, there has been an explosion in the field of computer science to solve various problems from mathematics to engineering. This journal aims to provide a platform for exchanging ideas in new emerging trends that needs more focus and exposure and will attempt to publish proposals that strengthen our goals.

Topics of interest

  • Algorithms
  • Automata and Formal Languages
  • Novel Data structures
  • Combinatorial Games
  • Computational Complexity
  • Programming Languages
  • Computational Number Theory
  • Cryptography
  • Database Theory
  • Queuing Methods
  • Distributed & High Performance Computing
  • Computer Security
  • Program Semantics and Logic

Probabilistic Methods

  • Computation Biology
  • Internet & Cloud Computing
  • Software Engineering
  • Artificial Intelligence
  • Biochemistry
  • Astrophysics
  • Geometric Modeling, Graphics and Visualization
  • Other Emerging applications

Paper Submission

Authors are invited to submit papers for this journal through E-mail: ijfcstjournal@wireilla.com . Submissions must be original and should not have been published previously or be under consideration for publication while being evaluated for this Journal.

Important Dates

  • Submission Deadline    : August 13, 2022
  • Notification                  :  September 13, 2022
  • Final Manuscript Due   :  September 21, 2022
  • Publication Date  : Determined by the Editor-in-Chief

Contact us :

Here’s where you can reach us : ijfcstjournal@yahoo.com (or) ijfcstjournal@wireilla.com

 

A Survey to Real-Time Message-Routing Network System with KLA Modelling

 

Paul T. Chiou, Yu Sun and G S. Young

 

Department of Computer Science, California State Polytechnic University, Pomona, California US

Abstract

 

Messages routing over a network is one of the most fundamental concept in communication which requires simultaneous transmission of messages from a source to a destination.  In terms of Real-Time Routing, it refers to the addition of a timing constraint in which messages should be received within a specified time delay.  This study involves Scheduling, Algorithm Design and Graph Theory which are essential parts of the Computer Science (CS) discipline.  Our goal is to investigate an innovative and efficient way to present these concepts in the context of CS Education.  In this paper, we will explore the fundamental modelling of routing real-time messages on networks.  We study whether it is possible to have an optimal on-line algorithm for the Arbitrary Directed Graph network topology.  In addition, we will examine the message routing’s algorithmic complexity by breaking down the complex mathematical proofs into concrete, visual examples.  Next, we explore the Unidirectional Ring topology in finding the transmission’s “makespan”.Lastly, we propose the same network modelling through the technique of Kinesthetic Learning Activity (KLA).  We will analyse the data collected and present the results in a case study to evaluate the effectiveness of the KLA approach compared to the traditional teaching method.

 

Keywords

 Real Time Routing, Routing Messages, Network Routing, Graph Theory, Scheduling, Arbitrary Directed Graph, Unidirectional Ring, Kinesthetic Learning Activity, KLA, CS Education

 

1. Introduction

 

In the age of multimedia today, almost everything is transferred through the Internet.  As the quality of multimedia rapidly increases over the past decade, the demand for a faster network bandwidth is also growing at a significant rate.  There are many applications relying on real-time routing services.  For instance, in a live messaging system, each participant interacts with the others by sending and receiving messages in the form of texts, pictures, audio sequences, or video frames [1].  Each message, originating from a participant, must be delivered to all the others in a real-time manner.  All these real-time systems are constantly in need to optimize their Quality of Service provided to the users [2].The transfer speed is bounded by the network infrastructure itself in the hardware level.  However, it is essential to theoretically understand how these routing take place so we can attempt to optimize for a more efficient algorithm.  This is indeed an area of research for CS students that crosses multiple domains such as Scheduling, Algorithm Design, Complexity Analysis, NP Theory, Graph Theory, etc. According to the ACM and IEEE, CS Education is a pathway to innovation and creativity that requires an understanding of the fundamentals problem-solving methodology of computational thinking [3].  In our research, we will introduce the model of a real-time system and present its method for scheduling messages.We shall then propose and incorporate our own modelling technique using the innovative non-traditional KLA to attempt a more effective learning approach for CS Education.

2. Introduction to Real-Time Message Routing

 

As mentioned, in a distributed real-time system, the problem of determining whether a set of messages can be sent on time becomes an important issue.  In the last two decades, real-time message routing has been studied extensively on various types of networks [4].  An on-line routing algorithm is one that routes messages without any knowledge of future arrivals of messages.  Based on the different level of constraints, the complexities can vary from easy (being solvable in polynomial time) while others are NP-hard [5].  Next, we shall first introduce the fundamental notion of various restrictions of the four parameters-  origin node, destination node, release time, and deadline.

 

2.1. The Formal Model and Notation

 

Wewill follow the scheduling standard and represent a network by a directed graphG=V, E shown in Figure 1, where each vertex in the setV represents a node of the network and each directed edge in setE represents a communication link.  Ifu, v∈E, then there is a transmitter in node u and a receiver in node v dedicated to the communication link u, v in Figure 2.  We assume that a node can simultaneously send and receive several messages if they are transmitted on different communication links [6].

 

Z61hc4RC_img1.png

 

 

Figure 1.  Network as a Directed Graph (Left),Communication Link (Right)

 

In our rounding problem, a set of n messages M=M1, …, Mn as shown in Figure 3 needs to be routed through the network.  Each message Mi consists of its own characteristic properties represented by a quintuple si, ei, li, ri, di.  In this set, the si denotes the origin node(i.e., Mi originates from node si), ei denotes the destination node (i.e., Mi is to be sent to node ei), li denotes the length (i.e., Mi consists of li packets of information), ri denotes the release time (i.e., Mi originates from si at time ri), and di denotes the deadline (i.e., Mi must reach ei by time di).  These features are the constraints in which we will follow to vary the message routing complexity.  The examples of these message routing problems consist of a network G and a set of messages M.  In our model, we further assume that it takes one unit of time to send a packet through a communication link.  This implies that it takes length li time units for message Mi to traverse on any communication link.  Also, there exists a central controller which has complete information on the topology of the network and the characteristics of each messages in advance.  Our goal is to determine if the messages in M can be routed through the network G such that each message Mi is sent from node si to node ei satisfying the given time interval of ri, di [5], [6].

 

2.2. Message-Routing Network System

 

A message-routing network system is a given system that consists of the network itself and the messages to be transmitted across it.  In notation, we let MRNS=G, M be the “Message-Routing Network System”, where G=V, E is a network and M=M1, M2, …, Mn is a set of n messages to be routed through G.  [5], [6].

A transmission S for MRNS is said to be feasible if the deadlines of all the messages are met; i.e., for all q=u, v, Mi, t1, t2, t2≤di. Here, t2 is the finishing time of the communication link.  A non-preemptive transmission, denoted by SNP, is a transmission such that for each configurationu, v, Mi, t1, t2∈SNP, t2-t1=li.  A preemptive transmission, denoted by SP, is a transmission defined exactly as before.  A MRNS is feasible with respect to non-preemptive (preemptive) transmission if there is a feasible non-preemptive (preemptive) transmission for MRNS [6].

 

3. Real Time Routing Complexity Analysis

 

3.1. Arbitrary Directed Graph

In this section, we present a Message-Routing Network System MRNSwith an arbitrary directed graph as shown in the Figure 2.  We let MRNS=G, M, where G is a network given and M=M1, M2, M3, M4.  The four messages to be transferred are defined with the following constraints:  M1=1, 4, 3, 0, 6, M2=1, 4, 2, 2, 6,M3=(3, 5, 2, 0, 6), and M4=(4, 5, 4, 0, 4).  The table in Figure 9 shows an organized view.  Recall the quintuple defined si, ei, li, ri, di which represents the origin node, destination node, length, release time, and deadline [5, 6].

 

 

Figure 2.  Arbitrary Directed Graph Network

 

Mi

si

origin node

ei

destination node

li

length

ri

release time

di

deadline

M1

1

4

3

0

6

M2

1

4

2

2

6

M3

3

5

2

0

6

M4

4

5

4

0

4

Table 1.  Message Constraints of M for the Arbitrary Directed GraphMRNS.

 

3.1.1. Non-Preemptive Transmission

 First, we will examine a non-preemptive instance of the MRNS.  In non-preemptive transmission, once a message is transmitted on acommunication link u, v, it must continue until the entire message is received by node v.  We use the subscript NP to denote the transmission S is non-preemptive.  With the message constraints in Table 1, we can construct the following transmission

SNP={(1, 2, M1, 0, 3), (2, 4, M1, 3, 6), (1, 3, M2, 2, 4), (3, 4, M2, 4, 6), (3, 4, M3, 0, 2),

(4, 5, M3, 4, 6), (4, 5,M4, 0, 4)}, as shown in Figure 3 [6].

 

 

Figure 3.  Feasible Non-Preemptive Transmission for MRNS.

 

M1, M2 are departing from their origin node 1 to reach destination node 4.  For this transmission, M1 will take route 1→2→4and M2 will take route 1→3→4 since this will be more efficient having both messages transferred simultaneously during time 2 to 3, 3 to 4, and 4 to 6.  Note that at time 0, messagesM1, M3, M4 are released from their origin nodes 1, 3, 4 respectively.  Each of the corresponding message lengths are 3, 2, 4.  Therefore, messages M1, M3, M4 arrives at node 2, 4, 5 at times 3, 2, 4.  Since M4’s destination node is 5, its transfer is then complete at time 4.  While M1, M3, M4 are transferring at time 2, M2 is ready to be released and it takes 2 units (its length) time for it arrive at node 3At time 3, when M1 finishes arriving at node 2, it can begin its transfer to its destination node 4. At time 4, when M2 finishes arriving at node 3, it can begin its transfer to its destination node 4.  Note that the communication link 4, 5 is being occupied by M4 so M3 must wait until it finishes (considering this is a non-preemptive transmission).  Finally, M3 begin its transfer to its destination node 5 along with M1, M2 [6].Clearly, SNP is a feasible non-preemptive transmission because all messages met their deadlines.  Thus, with this example, we can conclude this MRNS is feasible with respect to non-preemptive transmission.

 

3.1.2. Preemptive Transmission

Unlike non-preemptive where all messages must finish its transfer once it starts, preemptive transmission can be interrupted and resume later.  This provides more flexibility and can be more efficient although it adds complexity to the problem.  In fact, if a MRNS is feasible with non-preemptive transmission, it is also feasible with preemptive transmission [6].

 In the following example, we will slightly modify the previous instance to demonstrate the preemptive transmission case.  Consider a new system MRNS’ obtained from MRNS by modifying M4 to be 4, 5, 2, 3, 5.  Now M4 has a shorter message length of 2 and later deadline of 5.  However, its released time is postponed to 3Table 2shows the change in grey.

 

Mi

si

origin node

ei

destination node

li

length

ri

release time

di

deadline

M1

1

4

3

0

6

M2

1

4

2

2

6

M3

3

5

2

0

6

M4

4

5

2

3

5

Table 2.  Modified Message Constraints of M for MRNS’

 

This time in MRNS’, messages M1, M2 remains unchanged asM4 does not affect them.   However, M4 is constrained and cannot be released until time 3.  When M3 finishes transferring to node 4 at time 2, it can begin its transfer to it destination node 5without being idling between time 2 to 3.  Now at time 3,M4 is released and since this is preemptive transmission, M3 can be interrupted to continue later.  Hence,M4 begins and finishes arriving at its destination node 5 after 2 time units(its length).  Finally, the interrupted M3 can now resume its transfer, completing at destination node 5attime6.Thetransmission

S’P{(1, 2, M1, 0, 3), (2, 4, M1, 3, 6), (1, 3, M2, 2, 4), (3, 4, M2, 4, 6), (3, 4, M3, 0, 2), (4, 5, M3, 2, 3),

(4, 5, M3, 5, 6), (4, 5, M4, 3, 5)}, is a feasible preemptive transmission.  However, the modification made it not feasible with respect tonon-preemptive transmission.  By examining Figure 4, we see the reason is due to M3.  At time 3 when M4 is ready to be released, without preemption, M3 must keep transferring until it finishes at time 4 occupying communication link (4, 5) and M4 must wait.  When M4 is finally able to begin transfer at time 4, its message length of 2 will result a finishing time of 6, therefore missing its deadline at time 5.  Thus MRNS’ is feasible with respect to preemptive transmission, but notnon-preemptive transmission [5], [6].

 

 

Figure 4.  Non-feasible Preemptive Transmission for MRNS’

 

3.1.3. Theorem and Proof

We now show that if the network is an arbitrary directed graph, the problem of determining whether there is a feasible transmission (both preemptive or non-preemptive) for a message-routing network system is NP-complete.  The hardness is not caused by the message constraints but the nature of the network topology because it is NP-complete even when all four parameters are fixed [6].  Consider the following theorem: 

3.1.3.1 Theorem 37.1

Given MRNS=(G, M), where G is an arbitrary directed graph and M is a set of messages with identical origin nodes, destination nodes, release times, and deadlines, the problem of determining whether MRNS is feasible with respect to preemptive transmission is NP-complete [6].

The theorem can be proved by the reduction from the3-Partition problem, which is known to be strongly NP-complete.  Before showing the proof, we will explore the3-Partition problem.The 3-partition problem is a problem where one should partition 3z numbers (allowing duplicates) into z groups of 3, such that each group has the same sum.  If all 3z numbers sum to N, this means that every group should have a sum of N/z.  The 3-partition problem is a well-known NP-complete problem.  Next, we use formal notation to precisely define the problem [6, 7].

 Given a list, A=a1, a2, …, a3z of 3z positive integers such thati=13zai=zBand each ai satisfyingB4<ai<B2 for each 1≤i≤3z,  can I=1, 2, …, 3z be partitioned into z groups of 3, I1, I2,…, Iz such that i∈Ijai=B     for each 1≤j≤z (each group sums to exactly B).

 

The 3-partition problem is similar to the partition problem, which in turn is related to the subset sum problem.  In the partition problem, the goal is to partition S into two subsets with equal sum. In 3-partition the goal is to partition S into z subsets, not just two subsets, with equal sum [7]. 

To show that the decision problem is in NP, notice that preemption is necessary only when a new message arrives at a node.  Thus, the number of preemptions is bounded by a polynomial function of the size of the input, and hence we can guess a preemptive transmission in polynomial time and verify that the transmission is feasible [6].  To complete the proof, the 3-Partition problem reduction can be defined as follows:

 Let A=a1, a2, …, a3z be an instance of the 3-Partition problem. We construct an instance of the message routing problem as follows: MRNS=(G, M), where

 G=0, 1, 2, …, z+1,0, 1, 0, 2, …, 0, z,1, z+1, 2, z+1, …, z, z+1

and M=(M1, M2,…, M4z), andMi=0, z+1, ai, 0, 5B for each 1≤i≤3z and Mi=0, z+1, 2B, 0, 5B  for each 3z+1≤i≤4z. We call the first 3z messages the partition messages and the remaining z messages the enforcer messages [5].  This is visually represented in Figure 5

 

 

Figure 5.  Visual Representation of G and M for 3-Partition MRNS

 

Clearly, based on the definition, all messages in M have identical origin nodes, destination nodes, release times, and deadlines.  Thus, construction can be done in polynomial time.  Since the hard 3-partition is given by the oracle, the hard-part is done.  The polynomial construction simply involves calculating the extended message length and mapping the nodes.  Adding the enforcers is also be done in polynomial time [6].For the reduced instance, there are z distinct paths from vertex 0 to vertex z+1 in G. In any feasible transmission for MRNS, each enforcer message must be routed along a distinct path from vertex 0 to vertex z+1. The remaining partition messages must be distributed among these z paths [6]. This is intuitively correct because the enforcer messages essentially “jams up” each of the route, reducing the complexity and possibilities of combinatorically assigning the partition messages.The above MRNS is feasible with respect to preemptive transmission if and only if A has a 3-Partition.  We now show the case with a substantial instance of the reduction process.  The following is a “yes”’ instance of the 3-partition of 3z messages with z=3.  Notice that our B=100, which is the sum of each partition with the elements satisfying size 1004<ai<1002.  Otherwise, it would be impossible to have 3 parts each [7].

A=a1, a2, a3, a4, a5, a6, a7, a8, a9=26, 29, 33, 33, 33, 34, 35, 36, 41

I1=a1, a3, a9=26, 33, 41

I2=a2, a8, a7=29, 36, 35

I3=a4, a5, a6=33, 33, 34

 These 3z elements maps to the corresponding partition messages.  We then add z more messages M10,M11,M12 as the enforcer messages.  The set M now consists of 4z messages:

 

M=M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12

 

Figure 6.  Message Constraints of M for 3-PartitionMRNS

Suppose I1, I2…, Iz is a solution to the 3-Partition problem.  We can construct a feasible non-preemptive (and hence preemptive) transmission as follows [6].

  • For each 1≤j≤z, the messages M3z+jand Mi, where i∈Ij, are transmitted from node 0 to node z+1 through the edges 0, jand j, z+1.  Shown in Figure 7.
  • M3z+jis transmitted through the edges 0, jand j, z+1 in the time intervals 0, 2B and 2B, 4B respectively.  Shown in Figure 8 (left).
  • The messages Mi, where i∈Ij, are nonpreemptively transmitted through the edges 0, jand j, z+1 in the time intervals 2B, 3B and 4B, 5B, respectively.  Shown in Figure 8 (right).

 

Using the above algorithm, we created a feasible non-preemptive transmission using the properties of our 3-partition instance as follows

 

 

Figure 7.  Message Categorization of the Partitions.

 

  • For j=1, M10, M1, M3, M9 are transmitted from node 0 to node 4 through the edges 0, 1 and 1, 4 with M10 in the time intervals 0, 200 and 200, 400 and M1, M3, M9 non-preemptively transmitted in the time intervals 200, 300 and 400, 500
  • For j=2, M11, M2, M8, M7 are transmitted from node 0 to node 4 through the edges 0, 2 and 2, 4 with M11 in the time intervals 0, 200 and 200, 400 and M2, M8, M7 non-preemptively transmitted in the time intervals 200, 300 and 400, 500
  • For j=3, M12, M4, M5, M6 are transmitted from node 0 to node 4 through the edges 0, 3 and 3, 4 with M12 in the time intervals 0, 200 and 200, 400 and M4, M5, M6 non-preemptively transmitted in the time intervals 200, 300 and 400, 500

 

Figure 8.  Messages’ Distinct Paths (Left), and Transmission Times (Right)

 

Path distinctness in the proposed MRNS can be show by supposing S is a feasible preemptive transmission for MRNS. Observe on the left of Figure 8 that there are exactly z distinct paths from node 0 to node z+1; namely, P1=0, 1, z+1,  P2=0, 2, z+1, …, and Pz=0, 3, z+1 [6].  In our case, there are exactly 3 distinct paths from node 0 to node 4 which are P1=0, 1, 4,  P2=0, 2, 4, and P3=0, 3, 4.With these distinct paths, each message must be transmitted through one of these z paths and if two enforcer messages are transmitted through the same path in S, then one of them will arrive node z+1 at time 6B or later, and hence it will miss its deadline.  Thus, we may assume that no two enforcer messages are transmitted through the same path in S [5, 6].  In our case, notice if two enforcers are transmitted through the same path, one of them will arrive node 4after the deadline600.  This can be generalized for each path1≤j≤z, we let Ij=i | 1≤i≤3z and Mi is transmitted through Pj in SThus, for j=1,I1=a1, a3, a9 and M1, M3, M9 are transmitted through P1;  for
j=2, I2=a2, a8, a7 and M2, M8, M7 are transmitted through P2 ;for
j=3, I3=a4, a5, a6 and M4, M5, M6 are transmitted through P3.  Clearly, this is a feasible non-preemptive transmission as shown on the right of Figure 8. Therefore, MRNS is feasible with respect to preemptive transmission.

 

3.1.3.1.1.Proof by Contradiction 

We have shown the theorem works for one case.  To show that it holds true for all cases, we provide a generic proof.  We claim that I1, I2,…, Iz is a solution to the 3-Partition problem. If the claim is not true, then there is an index k such that i∈Ikai>B.  In other words, Ik is the 3 set whose sum exceeds B=100. Let X∪M’ be the set of messages transmitted through the path Pk in S, where X=Mi | i∈Ik and M’ is the enforcer message.  Let t’ be the time instant at which M’ is completely transmitted to node k, and let X1 and X2 be a partition of X such that X1 and X2 contain all the messages in X that are completely transmitted to node k before and after time t’, respectively [6].Clearly, the total time taken to transmit all the messages in X∪M’ is defend in the relationship:t’+2B+Mi∈X2li≥Mi∈X1li+2B+2B+Mi∈X2li=4B+Mi∈Xli>5BWe can interpret the above inequity by dividing the terms into 3 groups.  The first group denoted by t’+2B+Mi∈X2li is the time (t’) the enforcer message M’ spent on the first link 0, k to completely arrive at the intermediate node k.  This is summed with 2B (the length of M’) and the total time (length) of the partition messages to completely arrive to the destination (Mi∈X2li) on the next link k, e.  The second group denoted by Mi∈X1li+2B+2B+Mi∈X2li is to account for the scenario if there are partition messages that arrives to intermediate node k before the enforcer message M’ does at t’.  This portion spent on the first link 0, k is Mi∈X1li plus the M’ itself.  This Mi∈X1li+2B is then summed with 2B+Mi∈X2li all the time span on the next link k, e as previously discussed.   The third group is just algebraic manipulation but is equally expressed as the total time M’ spent (2B+2B) on both links 0, k and k, e plus the total time all other message spent denoted by Mi∈Xli [6]. In our first non-preemptive example, analysis is trivial because all partition messages always arrive after the enforcer message finish arriving node k at time t’ so set X1 is empty.  This can be seen in Figure 9.  Hence, 200+2B+100≥0+2B+2B+100=4B+100>5B.  Here, we have X1=∅ and M1, M3, M9∈X2 for path P1=0, 1, 4; X1=∅ and M2, M8, M7∈X2 for path P2=0, 2, 4; and X1=∅ and M4,M5,M6∈X2 for path P3=0, 3, 4;

 

 

Figure 9.  Non-Preemptive Transmission I (Enforcer First)

 

The following transmission in Figure 10 is another non-preemptive instance where some partition messages arrive before the enforcer message finish arriving node k at time t’.  We have M1∈X1 and M3, M9∈X2 for path P1=0, 1, 4; M2, M8, M7∈X1 and X2=∅ for path P2=0, 2, 4; and M5, M4∈X1 and M6∈X2 for path P3=0, 3, 4;

 

 

Figure 10.  Non-Preemptive Transmission II (Mixed Order)

 

According to the definition, transmitting preemptively works as well.  The following Figure 11 shows a preemptive instance.  Notice for the first link 0, 2 of route P2, M8 was chopped and began transfer later after the enforcer M11 (which was also chopped several times).

 

Figure 11.  Preemptive Transmission I (Feasible)

 

These feasible transmissions are essentially best-optimal solutions.  However, the whole purpose of such proof is to show that it is possible to have a non-optimal solution which exceeds 5B.  The next example Figure 12 in take the previous in Figure 11 and slightly delays M6.  Noticed now M6 on link 3, 4 must also be delayed because it cannot start until M6 is fully received on node 3.  This then delays the enforcer M12, ultimately causing M5 to miss the deadline (shown in red).

 

 

Figure 12.  Preemptive Transmission II (Non-Feasible)

 

Thus, at least one of the messages in X∪M’ has its deadline missed, contradicting our assumption that S is a feasible transmission.  We showed it with a counter-example and since MRNSis feasible with respect to preemptive transmission if and only if Ahas a 3-Partition, if S is not feasible, therefore it is at least as hard as 3-partition [6].

 

3.1.3.2. Corollary 37.1

 

Given MRNS=(G, M), where G is an arbitrary directed graph and M is a set of messages with identical origin nodes, destination nodes, release times, and deadlines, the problem of determining whether MRNS is feasible with respect to non-preemptive transmission is NP-complete [6].Based on the previous examples, we clearly see that the Theorem 37.1 also works with non-preemptive transmission. Thus, Corollary 37.1.  In fact, later in Section 4.2.2, we will show that all non-preemptive transmissions are literally preemptive transmissions. 

3.2. Unidirectional Rings

In the previous section, the Theorem and Corollary have shown the message routing problem a computationally hard problem if the network is allowed to be arbitrary (Arbitrary Directed Graph).  We now relax we our focus to the simpler network topology class of Unidirectional Rings in order to find the minimal makespan of the routing system.  This is the simplest method in demonstrating scheduling routing in any given MRNS.  The following Figure 13 shows the network complexity hierarchy [5, 6].

 

Figure 13.  Unidirectional Ring Network (Left), Network Complexity Hierarchy (Right)

 

First, we will introduce the following additional notations and terminologies:

A simple network of “Unidirectional Ring” G is defined to be G=V, E, where V=1, 2, …, m for some integer m>1 and E=1, 2, 2, 3, …, m-1, m, m, 1 with m nodes [6].Let S be a transmission for MRNS=G, M, where G is a Unidirectional Ring with m nodes and M is a set of n messages.  We use fMi, S to denote the finishing time of Mi in S.  For example, recall the configuration q=u, v, Mi, t1, t2, we have t2 as the finishing time.  In this case,fMi, S=maxu, v, Mi, t1, t2∈St2, the finding time of the message Mi.  The makespan of S, denoted by MSS is defined to be max1≤i≤nfMi, Sacross all messages [6].

 

In our network example as shown on the left ofFigure 13, we have V=1, 2, 3, 4 and E=1, 2, 2, 3, 3, 4, 4, 1 with 4 nodes.

 

3.2.1. Preemptive Transmission

 3.2.1.1. Lemma 37.1

 Let SP be a feasible preemptive transmission for a set of messages with the same origin node, destination node, release time, and deadline. If the common origin node and destination node of all the messages are 1 and e, respectively, then we have MSSp≥i=1nli+e-2max1≤i≤nli [6]. For a set of messages with identical origin nodes, destination nodes, release times, and deadlines.  Lemma 37.1 gives a lower bound for the makespan of any feasible transmission (both preemptive or non-preemptive).  Before generalization, we will first provide an instance to better visualize the MRNS.  Consider the following

 

Mi

si

origin node

ei

destination node

li

length

ri

release time

di

deadline

M1

1

4

2

0

14

M2

1

4

3

0

14

M3

1

4

2

0

14

M4

1

4

1

0

14

 

Table 3.  Message Constraints of M for the Unidirectional Ring MRNS

 

If the lemma is not true, then there is a feasible preemptive transmission Sp such that MSSp<i=1nli+e-2max1≤i≤nli.  Without loss of generality, we may assume that the common release time of the messages is time 0. Let MP be the longest message; i.e., lp≥li for each 1≤i≤n.  For each 2≤j≤e, let tj be the time instant at which MP is completely transmitted to node j on the edge j-1, j in Sp.MSSp<i=1nli+e-2max1≤i≤nli [6].In our example, we have 14<2+3+2+1+23.  In the following example, in Figure 14, the red lines represent the time instant that the longest message MP=M2 is completely transferred to node 2≤j≤e.

 

 

Figure 14.  Time Instants tj of SNP (Top) and SP (Bottom)

 

The top instance in Figure 14is the non-preemptive SNPwith tj=t2=5 (the time M2 completely transmitted to node 2 on the edge 1, 2), tj=t3=8 (to node 3 on the edge 2, 3), and te=t4=11 (to node 4 on the edge 3, 4),  the bottom instance is the preemptive SP with tj=t2=5, tj=t3=12, and te=t4=16.It is obvious that te=fMp, Sp.  In our non-preemptive instance, the common destination node e=4.  So, the time to finish transfer the longest message Mp at t4 is also the completion time ofMpon the last communication link (edge) [6].Next, we will categorize the messages into two categories based on the following definition.For each 1≤i≤n and 2≤j≤e, let X(i, j) and Y(i, j) be the total amounts of Mi transmitted on the edge j-1, j in Sp in the time intervals 0, tj and tj,MSSp, respectively.This yields the two message categories X(i, j) and Y(i, j) for the non-preemptive transmissionSNP shown on the left of Figure 15 and for the preemptive transmission SP shown on the right.  We haveXi, j+Yi, j=li for each 1≤i≤n and 2≤j≤e since each message is either transmitted before or after tj.

 

 

Figure 15.  X(i, j) and Y(i, j) of SNP (Left) and SP (Right)

 Next, we will categorize the messages into 3 sets.  Each set has a distinct characteristic which will play in a role in determining the makespan MSSp of our transmission.  We will define set A, B, C as follows [6]A=Mi  |  Miis completely transmitted to node 2 beforet2inSp

It is clear that the messages in set A accounts for the time (length) exclusively between node 1 and node 2 on link 1, 2 that finishes arriving at node 2 before Mp (the longest message) does.

 

B=Mi  |  Miis completely transmitted to node 2 aftert2inSp, andMiis completely transmitted to node k beforetkfor some node k, 3≤k≤e

 The messages in set B is the ones that arrives after Mp to node 2 but later actually beats (finishes arriving earlier than) Mp on a later node (potentially any node from 3 to the destination node e). 

 C=Mi  |  Miis completely transmitted to node j aftertjinSpfor each 2≤j≤e

 The messages in set C are the ones that arrives after Mp does to any node ranging from node 2 to the destination node e.  The total message length in all these 3 cases in fact, sum up to the entire span (makespan) of our preemptive transmission Sp.

 

 

Figure 16.  Sets A, B, C of SNP (Top) and SP (Bottom)

 

By our definitions, the sets A, B, C, and Mp are pairwise disjoint, and the set A∪B∪C∪Mp  contains all the messages.  Note that Mp itself is not included in any of the sets A, B, C.With our SNP, the sets for our instance is the follows with B being the empty set containing no messages.   A=M1,     B=∅,     C=M3, M4.  On the other hand, with our SP, the sets for our instance is the follows with B being the empty set containing no messages.   A=M1,     B=M3,     C=M4.We now compute a lower bound for fMp, Sp (or equivalently, te).  This is the shortest/least possible time for the longest message Mp to finish transfer to the destination node.   We will examine how these 3 sets of messages A, B, C form the entire makespan.  So far, we have three types of messages: [5, 6]

  • Each Mi∈A is completely transmitted to node 2 beforeMp does, and hence it delays the finishing time of Mp by at least li amount.
  • For each Mi∈B, there is a node k, 2≤k<e, such that Mi is completely transmitted to node k after Mp does, but it is completely transmitted to node k+1 before Mp does.  Thus, it again delays the finishing time of Mp by at least li amount.Each Mi∈C is completely transmitted to node j, 2≤j<e, after Mp does. However, the total amount transmitted on the edgee-1, e by time te is Xi, e, and hence it delays the finishing time of Mp by at leastXi, e amount of time.

 

Recall that every message M1≤i≤n is also divided into 2 groups,X(i, j) andY(i, j)representing their total amounts being transmitted on the edge j-1, j for all edges 2≤j≤e in Sp.   X(i, j) is the portion between time intervals 0, tj and Y(i, j) between tj,MSSp.  In other words, X(i, j) and Y(i, j) arrives before and afterMp does respectively.

 The properties above for Mi∈A and Mi∈B are self-explanatory.  ForMi∈C, we this property so the entire set C consists of 2 parts of Mi∈CXi, j∪Mi∈CYi, j.  Moreover, it is specifically used to account for the case of Xi, e whenMp is preemptively chopped in the last edge e-1, e.  Hence, there exists some message Mi∈C that has a portion being transferred before Mp finishes at te.  This is the last portion to be included in fMp, Sp as shown in By referring to Figure 30, we see that our B=∅.  In our example 1,X1, 4=2, X2, 4=3, X3, 4=0, X3, 4=0 and only M3 and M4 are in C (since by definition, they finished arriving after time te).  Therefore, Mi∈CXi, 4=0.

 

3.2.1.1.1. Direct Proof

Putting it altogether, we are able to directly proof the Lemma 37.1.  We will also show it works for both our SNP and SN instances.  From the above we see the finishing time of Mp is essentially te, which is greater than or equals the sum of the following three parts:

 

  1. Total span (delay) of the messages in set A (denoted by Mi∈Ali)Total time to send Mp through number of edges (from node 1 to e) denoted by e-1lp
  2. Total span (delay)of the messages in set B(denoted by Mi∈Bli)
  3. Total time of the messages in set C that has part of it transferred before Mp finishes at te on edge e-1, e.

(1)

fMp, Sp=te≥Mi∈Ali+e-1lp+Mi∈Bli+Mi∈CXi, e

 Now, we know the makespan MSSp has to be the finishing time of Mp (fMp, Sp) plus the time to finish the rest of the messages that complete after te (Mi∈CYi, e).  So, we have:

(2)

MSSp=fMp, Sp+Mi∈CYi, e

(3)

Substituting fMp, Sp with Mi∈Ali+e-1lp+Mi∈Bli+Mi∈CXi, e, 

Mi∈Ali+e-1lp+Mi∈Bli+Mi∈CXi, e+Mi∈CYi, e 

(4)

Combining the two parts of set C (parts partially transferred before te during preemption and the parts after te) since Mi∈CXi, e+Mi∈CYi, e=Mi∈Cli. (Recall Xi, j+Yi, j=li)

 =Mi∈Ali+e-1lp+Mi∈Bli+Mi∈Cli

(5)

Factor out a lp from e-1lp:

=Mi∈Ali+e-2lp+lp+Mi∈Bli+Mi∈Cli

 

(6)

By definition, the pairwise disjoint sets of A, B, C and Mp form the set of all messages (
ABC∪Mp=i=1nli).  CombiningA, B, C, 

=i=1nli+e-2lp

We know that the message of the longest length can be expressed as MP=lpwhich is the maximum of length li ofall message1≤i≤n

=i=1nli+e-2nmaxi=1li

(7)

Finally, we obtain what we proposed in the Lemma.  [6]

Figure17 illustrates the non-preemptive instanceSNP on the left and the preemptive instance SPon the right.  Both visually demonstrate each section of A, B, C in the above proof.

 

 

Figure 17.  Visual Representation of Proof for SNP (Left) and SP (Right)

3.2.2. Non-Preemptive Transmission

We have previously proved Lemma 37.1 for a particular case of non-preemptive and preemptive transmission.  In fact, all non-preemptive transmissions are literally preemptive transmissions.  It is just a special case by choosing not to utilize the preemptive functionality.  Non-preemptive transmissions are a subset of preemptive transmissions.  The following complexity hierarchy in Figure 18 shows the relationship between preemptive/non-preemptive.

 

 

Figure 18.  Non-Preemptive/Preemptive Complexity Hierarchy

 

This is just the rule of the general computational complexity.  We have preemptive transmissions as the more general case with fewer constraints (such that each transmission must not finish transferring completely before it can be transferred elsewhere on another communication link (link)).  Intuitively, we claim that:  If the more general case is easy, then the special case is easy; if the more special case is hard, then the general case is hard.  This brings our next lemma:

 

3.2.2.1. Lemma 37.2

Let SNP be a feasiblenon-preemptive transmission for a set of messages with the same origin node, destination node, release time, and deadline. If the common origin node and destination node of all the messages are 1 and e, respectively, then we have MSSNP≥i=1nli+e-2max1≤i≤nli. [6]

 This is obvious and the formal proof is as follows:

3.2.2.1.1. Direct Proof

Let S1 be a feasible non-preemptive transmission for the set of messages such that it has the minimum makespan among all feasible non-preemptive transmissions.  Let S2 be a feasible preemptive transmission for the set of messages such that it has the minimum makespan among all feasible preemptive transmissions [6].

 Since MSSNP≥MSS1≥MSS2, the lemma follows immediately from Lemma 37.1.

 

 

Figure 19.  Visualization of Proof for Lemma 37.2 

We can clearly see in Figure 19that by constructing S1 and S2, we intermediately show that the non-preemptive transmission (our claim SNP) is at least as efficient (at least as long in total transmission length makespan MSSNP) as the non-preemptive transmission S1 (its makespan MSS1) which is at least as efficient as those of the preemptive transmission S2 (its makespan MSS2) [6].  Therefore, we have showed:

MSSNP≥MSS1≥MSS2=MSSP≥i=1nli+e-2max1≤i≤nli

Which holds true for both preemptive and non-preemptive cases MSSP≥i=1nli+e-2max1≤i≤nli and MSSNP≥i=1nli+e-2max1≤i≤nli respectively for our Lemma 37.1 and Lemma 37.2 [6].

4 . Kinesthetic Learning Activity Model

 

Pereducation theory, one of the most challenging aspect lays in the theory of learning.  Learning theories are the conceptual frameworks in which knowledge is absorbed.  The primary learning technique in most academic disciplines is thetraditional learning that has been followed for ages.  This typical learning technique places students in apassive rather than an active role.  Traditional learning encouragesone way communication and therefore, the lecture must make a conscious effort to become aware of the students’ understanding without verbal feedback.  Furthermore, traditional learning requires a considerable amount of time outside of the classroom to enable a long-term retention of the content [8].

To overcome the shortcomings of traditional learning and to improve the performance of all types of students, we present a technique called Kinesthetic Learning Activity (KLA).  This interactive approach was first presented at California State Polytechnic University, Pomona(Cal Poly Pomona) [8].  Throughout the years of KLA implementation, research has shown substantial positive feedback from students as well as itseffectiveness proven by the quizzes conducted directly after.  Studies also show that students prefer a “hands on” or “learning by doing” approach to build understandings [8].  Below is the our proposed KLA specifically designed for our Real-Time Network Message Routing research.

 4.1. Overview of the Proposed KLA Approach

In our KLA, we want the students to actively engage in the material directly following our presentation to provide best learning outcome.  While the students may or may not comprehend the concepts of message routing over a MRNS, by using a “quiz” approach with hands-on, our KLA will stimulate the student’s creative thinking abilities.  We have developed a hands-on crafting activity using KitKat chocolate bars to simulate what the message routing configuration would be like under various preemptive/non-preemptive models.

The following Figure 20 shows the presentation slide of the KLA introduction on left.  On right is the slide detailing the assigned main activity.

 

 

Figure 20.  Presentation Slides

 

4.1.1. Learning Goals

 This study will examine the consequences of subjecting kinesthetic learning techniques on students enrolled in an upper division Computer Science course, CS331 Design and Analysis of Algorithms, at Cal Poly Pomona for the Summer 2017 academic quarter. Those results will be compared with the effectiveness of traditional instructional methods. The objective of this study is to provide evidence that kinesthetic learning activities supplement the learning and comprehension of course materials. Our hypothesis is that KLAs, when used to complement traditional classroom instructional methods will increase the amount of material absorbed by the students.  We suggest at the end of this exercise, students will be able to experience the practical aspect of constructing a feasible transmission (whether it be preemptive or non-preemptive) given a set of messages with certain constraints.  This research study has been reviewed and approved by the Cal Poly Pomona Institutional Review Board (IRB): protocol#17-116.  It is in compliance with federal and state regulations as well as the Cal Poly Pomona policies regarding the protection of the human subjects used in the research.

4.2. KLA Instructions and Topic Information

 4.2.1. KLA Execution Instructions

Students were given one pre-test to gauge the prior knowledge. The class will then be divided in halves.  Each half will alternately be taught using the traditional method and the kinesthetic method over two class sessions by a single instructor. Following each lecture, the class was given a post-test to evaluate the level of material comprehend.  Students were also asked to complete a survey afterin effort to gather opinions on the effectiveness of the KLA.

 

 

Figure 21.

 

During the KLA, each student was supplied a pack of 1.5-Ounce Kit Kat Bars (Milk Chocolate, but flavors may vary).  Each pack consists of 4 finger bars.  In addition, each participant would receive their own plastic knife, and edge/time table worksheet.  The activity provides students a MRNS with a diagram of an arbitrary directed graph G and a set of 4 messages M=M1,M2,M3,M4.  Students were instructed to construct a feasible non-preemptive transmission satisfying the network and message constraints table.  They were to simulate each message-span with the provided KitKat bars by crafting them into the appropriate length.  Moreover, they were to place the crafted message/KitKat over the correct edge/time slot on the worksheet. Students have 15 minutes to complete the exercise.  To add competitiveness, we added an additional constraint that disqualifies the students if they over-chop the message length into segments.   In other words, we do not allow “gluing” pieces together. Figure 21 shows the instructions slide on the left.  On the right is the solution slide.

 

4.3. Evaluation of KLA Results and Analysis

The pre/post-test consists of 2 questions where Question 1 has part a (total 12 points) and b (total 3 points).  The test provides a feasible MRNS transmission and asks the students to fill in the blanks with 4 given available options.  Question 2 is True or False (total 5 points).  The testhas a total possible score of 20 points shown as follows:

4.3.1. Pre/Post Evaluation Test

Consider the above feasible MRNS Routing Configuration.

                    1a.        Fill in each blue blank with one of the following choices (M1, M2, M3, M4, or N/A)        (2 points per blue blank)

                    1b.        Fill in each green blank with one of the following choices (M1, M2, M3, M4, or N/A)      (1 point each green blank)

                    2.          True/False (1 Point Each)

  1. By changing M4’s deadline to 5 will cause this MRNS to be non-feasible
  2. By changing M2’s release time to 3 will cause this MRNS to be non-feasible
  3. By changing M1’s origin node to 2, this MRNS will remain feasible
  4. By changing M1’s length to 3 and deadline to 4, this MRNS will remain feasible
  5. This MRNS is still feasible if the transmission becomes non-preemptive

The solutions of Question 1a & 1b is shown in Figure 22 and the solution of Question 2 is a) False b) False c) False d) False e) False.

 

 

Figure 22.  Solutions to Pre/Post-Test Question 1a & 1b.

 

4.4. KLA Experimental Results

 The results of our KLA turned out well.  Students all had a positive response to the activity.  The scores from the tests are anonymously recorded in Figure 23showingthe pre-test and post-test scores, the mean, median, max, min points and percentages, along with the total number points possible.  Overall, although the KLA half of the class had a lower score throughout, they improved more significantly than the traditional teaching half.

 

 

Figure 23.  KLA Pre/Post-test Results

 

Figure 24.  % of Average Test Scores & Learning Effectiveness

 

Figure 24shows the difference in the pre-test and post-test results and separates the traditional vs KLA groups. The improvement in the average score for the group that learned via the traditional method was 15.88%, while the KLA group saw their average score jump by 21.67%.

 

4.4.1. KLA Survey Feedback

At the end of our KLA trial, the total of 29 students completed the survey consisting the following questions:

  • Question 1: My overall evaluation of the kinesthetic learning activity (KLA) is (circle one): Excellent, Good, Fair, and Poor.
  • Question 2: Rate the following questions on a scale of Strongly Agree to Strongly Disagree:

          a)         I enjoyed the KLA experience.

                    b)         The kinesthetic activities were easy to understand.

                    c)         The kinesthetic activities were easy to follow.

                    d)         KLA is effective in helping me learn concepts.

                    e)         KLA helped me be more engaged in learning process.

                    f)          I would recommend KLA as an alternative way of teaching

 

The responses from Question 2 is shown in the bottom of Figure 25 indicating most the students had a favorable experience with the KLAs. There were very few responses of Disagree or Strongly Disagree.  This result is consistent with Question 1. At last, all students participated and enjoyed eating the KitKats.  It was a good attempt considering it was the first KLA involving food.  We have also discovered many improvements that we can make to better the learning outcome.

 

 

Figure 25.  Results of Survey Question 1 (Top) Question 2 (Bottom)

 

I:\TX7\127MSDCF\DSC03740.JPG

 

Figure 26.  Students Executing KLA in Action

 

5. Conclusions and Future Work

 

In our survey of routing real-time messages, we have considered the problem of how to construct a feasible transmission on a given MRNS if one exists.  In the case where the MRNS does not have a feasible transmission, we identified the specific constraints that caused it to miss the deadline.  In addition, we analyzed and proved the computational complexity of an Arbitrary Directed Graph network to be NP-complete even when all four parameters are fixed.  We then considered a simpler network which is a special case of the Arbitrary Directed Graph called a Unidirectional Ring.  The same complexity results hold for preemptive transmission.

 

Lastly, to better demonstrate this MRNS, we proposed a Kinesthetic Learning Approach way to model the scheduling with KitKat chocolate bars.  This KLA method promotes student interactivity and improves student learning by engaging a fundamental and easily conceived learning style.  As previous research suggest, courses on analysis of algorithms are ideally suited for KLAs due to the complexity of the subject matter and the ability to adapt algorithm steps into physical actions.  Our KLA results a positive feedback from the students.  In addition, our case study shows an improvement in pre-test/post-test scores to support its effectiveness.  For future work, we plan to expand our research to more offline routing variations as well as online routing of variable-length messages with more variations in network complexity such as out-tree, in-tree, bidirectional tree, and bidirectional ring.  We also plan to improve our KLA model by providing better instructions through video examples for better participating results.  We will compare the experimental results to quantitatively analysis on its effectiveness.

 

 

References

 

                    [1]         R. Koch, B. Peis, M. Skutella and A. Wiese, “Real-Time Message Routing and Scheduling”, TU Berlin, Institut f¨ur Mathematik, Straße des 17. Juni 136, 10623 Berlin, Germany,, 2017.

                    [2]         U. Shaw and B. Sharma, “A Survey Paper on Voice over Internet Protocol (VOIP)”, International Journal of Computer Applications, vol. 139, no. 2, pp. 16-22, 2016.

                    [3]         D. Hemmendinger, “The ACM and IEEE-CS guidelines for undergraduate CS education”, Communications of the ACM, vol. 50, no. 5, p. 46, 2007.

                    [4]         P. Mueller, “New Algorithm Significantly Boosts Routing Efficiency of Networks”, Phys.org, 2008. [Online]. Available: https://phys.org/news/2008-08-algorithm-significantly-boosts-routing-efficiency.html. [Accessed: 30- May- 2017].

                    [5]         J. Leung, T. Tam and G. Young, “On-Line Routing of Real-Time Messages”, Journal of Parallel and Distributed Computing, vol. 34, no. 2, pp. 211-217, 1996.

                    [6]         J. Leung, Handbook of Scheduling, 1st ed. London: Chapman & Hall/CRC, 2004, pp. 795-826.

                    [7]         S. Joosten, “Relaxations of the 3-partition problem”, Department of Applied Mathematics, University of Twente, Enschede, The Netherlands, 2011.

                    [8]         Alraddady, Sara, Danny Luong, and Gilbert Young. 2014. “A Study of Kinesthetic Learning Activities Effectiveness in Teaching Computer Algorithms.” The 2014 International Conference on Frontiers in Education: Computer Science & Computer Engineering. 400-406

 

Authors

 

 

 

 

Paul is a Graduate Student of Computer Science at Cal Poly Pomona.  His research interests include assistive technology for the disabled, software accessibility testing, web and mobile applications, and CS Education, etc.  He will be pursuing his Ph.D. in CS and wishes to one day become a CS Professor.

 

Yu SunDr. Sun Assistant Professor of Computer Science at Cal Poly Pomona.  His research interests include software engineering, cloud and mobile computing, etc.  Sun leads the research and development for numerous start-up companies.  He has a solid background in both the industry working at Amazon as well as academia working as a Post-Doc research associate at Vanderbilt University.

 

Gilbert S. YoungDr. Young Professor of Computer Science at Cal Poly Pomona.  His research interests include parallel and distributed computing, computer networks, algorithm design, scheduling, combinatorial optimization, etc.  Young is the creator of the KLA and has received the College of Science Distinguished Teaching Award for his innovative and continuous research on this alternative CS teaching approach.

 

 

wtayhcjhy