On-line Routing of Real-Time Messages on Computer Networks Messages routing over a network - simultaneous transmission of messages from a source to a destination. - can go multiple routes

Real-Time Routing - message routing with release time and deadline constraints Reference: Our Focus Difference in our study, is the network is not a complete Graph

Must go through intermediate nodes Focus on the complexity of the message routing problem under various restrictions of four parameters

origin node destination node release time deadline Notation/Terminology

Represent a network by a directed graph Edges (communication links) A node can simultaneously send and receive several messages transmitted on different communication links 1 3

2 4 Set of n messages origin node destination

node length release time deadline

Preemptive v.s Non-preemptive Non-preemptive transmission- a message once transmitted on a communication link (u, v) must continue until the entire message is received by node v. Preemptive transmission- transmission can be interrupted and resumed later Message-Routing Network System

Configuration q Message-Routing Network System (Example) G= M=

G= M= non-preemptive transmission feasible!

G= M= nonpreemptive transmission Not feasible!

Theorem 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 deadlines The problem of determining whether MRNS is feasible with respect to nonpreemtivea and preemptive transmission is NP-complete.

Proof to Theorem Show that if the network is an arbitrary directed graph, determining whether there is a feasible transmission (preemptive or nonpreemptive) for a message-routing network system is NP-complete, even when all four parameters are fixed. Our reduction is from the 3-Partition problem, which is known to be strongly NP-complete.

Recall: 3-partition NOT the Partition Problem (2-partition) with 3 parts. Definition: Definition in ENGLISH! The 3-partition problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum.

Unidirectional Ring In our example with m=4 nodes... Example: Unidirectional Ring fixed

Example: Non-preemtive vs Preemptive non-preemptive preemptive chopped

chopped OFFLINE ROUTING OF VARIABLELENGTH MESSAGES Algorithms

Algorithm A :Earliest Available Message Strategy. Algorithm B : Earliest Available Message and Farthest Destination Strategy Algorithm C : Earliest AvailableMessage and EarliestDeadline Strategy. Theorem A set of messages with identical origin nodes, release times, and

deadlines is feasible with respect to nonpreemptive transmission if and only if the transmission generated by Algorithm B is feasible. Algorithm D: (Earliest Available Message, Earliest Deadline, and Farthest Destination Strategy). Whenever a node is free for transmission, send that ready

message which is available at the node the earliest. If there is a tie, choose the one with the earliest deadline. If again there is a tie, choose the one with the farthest destination. Any further ties can be broken arbitrarily. Theorem A set of messages with three of the four parameters fixed

is feasible with respect to nonpreemptive transmission if and only if the transmission generated by Algorithm D is feasible Online Routing of Variable-Length Messages

Online Routing of Variable-Length Messages In online routing, each node in the network routes messages without any knowledge of the messages in the order nodes or the release times of the messages. The study of online routing is meaningful only when the release times of the messages are arbitrary. Online Routing of Variable-Length Messages

Algorithm D ( Earliest Available Message, Earliest Deadline, and Farthest Destination Strategy ). Whenever a node is free for transmission, send that ready message which is available at the node the earliest. If there is a tie, choose the one with the earliest deadline. If again there is a tie, choose the one with the farthest destination. Any further ties can be broken arbitrarily.

Online Routing of Variable-Length Messages Theorem: For a set of messages with identical origin nodes, destination nodes, and deadlines, Algorithm D is an optimal nonpreemptive (preemptive) online algorithm. Online Routing of Variable-Length Messages Theorem: No optimal nonpreemptive (preemptive) online algorithm can

exist for a set of messages with identical origin nodes and destination nodes. Online Routing of Variable-Length Messages Theorem : No optimal nonpreemptive (preemptive) online algorithm can exist for a set of messages with identical origin nodes and deadlines. Online Routing of Variable-Length Messages

Theorem : No optimal preemptive online algorithm can exist for a set of messages with identical destination nodes and deadlines. Online Routing of Variable-Length Messages Theorem : No optimal nonpreemptive online algorithm can exist for a set of messages with identical destination nodes and deadlines Online Routing of

Equal-Length Messages Online Routing of Equal-Length Messages Previous sections: message routing problem for a set of variablelength messages. This section we consider only equal-length messages. Ques is: - Is it possible to have an optimal online algorithm for the following

networks unidirectional ring, out-tree, in-tree, bidirectional tree, and bidirectional ring. Optimal Online Routing Algorithm: - An optimal nonpreemptive (preemptive) online algorithm is one that produces a feasible nonpreemptive (preemptive) transmission, whenever one exists. Online Routing of Equal-Length Messages

Four parameters - origin node - destination node - release time - and deadline. Notation used: quintuple notation, (si , ei , li , ri , di) quadruple notation, (si , ei , ri , di)

( lengths of messages, li , are equal) Online Routing of Equal-Length Messages Set of n unit-length messages M = {M1, ... , Mn} needs to be routed through the network. Mi -

is represented by the quadruple (si ,ei ,ri , di) si denotes the origin node (i.e., Mi originates from si). ei denotes the destination node (i.e., Mi is to be sent to ei), 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). *assume that release times and deadlines are integers, while the length of each message is

one unit Unidirectional Networks The three online algorithms are given below. 1. Earliest Deadline (ED) Algorithm. Whenever a communication link is free for transmission, send that ready message with the earliest deadline. Ties can be broken arbitrarily. 2. Farthest Away (FA) Algorithm. Whenever a communication link is

free for transmission, send that ready message whose destination node is the farthest away. Ties can be broken arbitrarily. 3. Smallest Slack Time (SST) Algorithm. Whenever a communication link is free for transmission, send that ready message with the smallest slack time. Ties can be broken arbitrarily. Unidirectional Networks Theorems below - show that the ED, FA, and SST algorithms are

optimal when one of the four parameters is fixed. Thm: The ED algorithm is optimal for a set of messages with identical destination nodes. Thm: The FA algorithm is optimal for a set of messages with identical deadlines. Thm: The SST algorithm is optimal for a set of messages with identical origin nodes. Thm: The SST algorithm is optimal for a set of messages with identical release times. Thm - shows that no optimal algorithm can exist if all four parameters

are arbitrary. Thm: No optimal algorithm can exist for a set of messages with all four parameters arbitrary. K inesthetic

L A earning ctivity modeling of routing real-time messages on networks

Traditional Learning Shortcomings

Hard to concentrate Easily distracted by the computers in front of you Passive rather than an active role One way communication without feedback Ineffective learn nothing! I dont feel awkward being on stage anymore.

Modeling Message-Routing Network System (MRNS) with KitKat Bars! Materials Required: 1.5 Ounce KIT KAT Bars Plastic Knifes Edge/Time Table Worksheet

KitKat KLA Challenge Provided a with the following arbitrary directed graph and a set of messages Using the network and message constraints table, construct a feasible non-preemptive transmission.

KitKat KLA Challenge Provided a with the following arbitrary directed graph and a set of messages Using the network and message constraints table, construct a feasible non-preemptive transmission.

KitKat KLA Challenge Simulate each message-span with the provided KitKat bar by crafting into the appropriate length. Place the crafted message/ KitKat over the correct edge/time slot on the worksheet. (Label each message/KitKat segment) WARNING! You lose if you chop the message length too short!

Hint: Plan in advance before cutting (no room for error). KitKat KLA Challenge ? KitKat KLA Challenge Solution: