Routing Real-Time Messages on Networks

Routing Real-Time Messages on Networks

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:

Recently Viewed Presentations

  • Heat and Plate Tectonics Inside the Earth  The

    Heat and Plate Tectonics Inside the Earth The

    Heat and Plate Tectonics Inside the Earth The part of Earth we live on is called the crust. This is a very tiny layer on the planet. Beneath that is the mantle. This is a semi-liquid layer that is very...
  • The History of Public Health - University of Florida

    The History of Public Health - University of Florida

    (see Module 2: Modern Mission of Public Health) John Snow and the Broad Street Pump Dr. Snow devised a simple map identifying the number and distribution of cases of the disease in the community and the specific water company serving...
  • Gateway Test Review BIOLOGY

    Gateway Test Review BIOLOGY

    Biology Review Go to http://www.usatestprep.com/front/login.php
  • Nutrition Focused Physical Assessment

    Nutrition Focused Physical Assessment

    Malnutrition. Malnutrition is fairly common in hospitals and can lead to delayed healing and increased length of stay and medical costs. Malnutrition and poor food intake are associated with prolonged hospital stay, frequent readmissions, and greater in-hospital mortality.
  • Presentation title - IOOF

    Presentation title - IOOF

    Issued by IOOF Investment Management Limited ABN 53 006 695 021 AFS Licence No.230524 as Trustee of IOOF Employer Super, a division of the IOOF Portfolio Service Superannuation Fund ABN 70 815 369 818. This is general advice only and...
  • TUGAS APLIKASI KOMPUTER Nokia 8800 Sapphire Arte

    TUGAS APLIKASI KOMPUTER Nokia 8800 Sapphire Arte

    KEKURANGAN NOKIA 8800 SAPPHIRE ARTE Harga mahal Tidak ada video call Limited edition Tidak ada memory external Tidak punya infrared Hanya tersedia satu warna saja ACCECORIS NOKIA 8800 SAPPHIRE ARTE - Baterai Nokia BL-4U - Charger Nokia AC-6 (microUSB) -...
  • The Failure of 20th Century Intelligence Robert David

    The Failure of 20th Century Intelligence Robert David

    The Failure of 20th Century Intelligence Robert David Steele Intelligence Coach [email protected] Updated 18 April 2006
  • Chemical weapons definition A substance , such as

    Chemical weapons definition A substance , such as

    Organisation for the Prohibition of Chemical Weapons (OPCW) The convention is administered by the Organization for the Prohibition of Chemical Weapons (OPCW), which acts as the legal platform for specification of the CWC provisions (the Conference of State Parties is...