INTELLIGENT EXTENSIBLE ROUTING FOR OVERLAY NETWORKS WITH .
Proceedings of the 13th IEEE International Conference on ComputerCommunications and Network, ICCN04, October 11-13, 2004, Chicago, pp93-100INTELLIGENT EXTENSIBLE ROUTING FOR OVERLAY NETWORKSWITH EMBEDDED CONSTRAINT RESOURCE PLANNING SHELL: ACASE STUDY WITH DEADLINE BASED PACKET FORWARDINGJaved I. Khan & Nouman BantanInternetworking and Media Communications Research LaboratoriesDepartment of Computer Science, Kent State University233 MSB, Kent, OH 44242 U.S.A.javed@kent.edu & nbantan@cs.kent.eduAbstractThis paper presents a fast near linear run-timesystem for customizable criteria based packetforwarding and route lookup. It presents the casefor deadline line based packet forwarding. Thissystem has been designed after the ConstraintResource Planning (CRP) methodology foralgorithm designs. The resulting near-optimumalgorithm operates within an extensible CRPshell and uses two pluggable scheduling andforwarding heuristics to produce near-optimalperformance. In this paper we present the shellarchitecture, the algorithm, and the simulationresults of this system for dead-line based packetforwarding.Key WordsShell interface, intelligent routing, temporalquality of service, forwarding, admission control,leverage, deadline1IntroductionThe need for time-constraint application (e.g.multimedia application) has created a wide areaof research. An efficient time routing algorithmwill make major contribution to this field ofstudy. Since the optimum deadline base packetscheduling has been shown to be NP-hard [1],any routing algorithm must be fast in order toserve the purpose of the original issue that isdelivering the data on time. In this research, wedefine a routing interface based on the heuristicsmanagement research in AI and planning. Veryfew work exists which uses AI incommunication research area. Upon thisinfrastructure, we present various algorithmswhich have been designed using the ConstraintResource Planning (CRP) methodology – aconstraint satisfaction heuristics system [5,10].Since this methodology proposes an optimizingshell rather than a final solution, future researchmight even produce better results than theoutcome of this paper.The proposed architecture serves as anoptimizing shell, which can form the basis forefficient custom, overlay routing optimizationcriteria at run-time. With the assumption thattotal knowledge of the network traffic isavailable in distributed fashion, the proposedshell can potentially be used for custom routeoptimization for overlay networks.1.1 Related WorkRouting is the key service embedded into thecurrent Internet layer. It has two majorcomponent- routing information propagation andforwarding. Most research in routing has beenconducted to find stable and scalable routepropagation algorithms. The transition to OSPFfrom RIP and the advent of BGP hasdramatically improved the scalability of routeinformation management. However, the researchon forwarding is relatively little and primarilyfocused on the design of efficient lookup tabledata structure [13,17,19]. It is highly unlikelyany temporal QoS can be provided withoutintelligent forwarding.There are now two principle approaches toprovide temporal quality of service- theIntegrated Service (int-service) approach and theDifferentiated Services (diff-service) approach[8]. The int-service has been based on per flowbased resource reservation and classification ofservices, admission control and policing [2,19].In the int-service paradigm, a number ofinteresting results on queuing behavior undercontrolled traffic admission have been reportedin [3,6,9]. One simple approach was introducedin [14] where multiple copies of the timeconstraint packet are admitted into the network.This approach increases the probability for ontime delivery, but it also increases the overallflow of traffic. The use of fixed input queue hastriggered a lot of research as well [1,2].Moreover the fixed input queue is beingimplemented in some current router architecture,e.g. Cisco routers.The other and more recent approach is the diffservice [4]. Instead of setting the service on perflow basis, packet flows are simplified into flow
Proceedings of the 13th IEEE International Conference on ComputerCommunications and Network, ICCN04, October 11-13, 2004, Chicago, pp93-100classes. Packets arrive with class labels and areaccordingly diverted in the appropriate queue(we will use the term queue instead of route).The packets from time-critical application willbe in a high priority queue that will then beprocessed first [15]. This heuristic provides highlevel of QoS. Both services architectures requiresubstantial modification of the IP routerarchitecture, where multiple queues have to bemaintained.Prior work that provides a high level of QoSwith the support the CRP methodology hadproduced excellent results when used incommunication research. We presented a CRPmethodology in a single hop overlay network in[11] where the outcome yielded exceptionallygood result over Greedy routing. This paperdiffers a great deal from [11] since otherelements like multi-hops, cost function, differentnetwork models, and many more areimplemented here.1.2 Intelligent RoutingThe existing research will show that most ofthem have been proposed with an implicitassumption that no intelligent action at thejunction points other than IP standard processingis permissible. The flow-based into a servicemodel essentially performs resource reservationand entry policing at the network endpoints.The diff-service has been a notable advancementwhere it has looked into standard basedextension. Intelligent routing inside the overlaynetwork was indeed a serious limitation- untilnow.However,recentadvancesinprogrammable networking such as OPENSIGand Active Network have shown some satisfyingresults [12,16], where network layer can becustomized. In the light of such advancements itseems that direct and more efficient solutions ofmany of the currently hard to solve problem arepoised to be developed, including networkmechanisms where deadline assured delivery isguaranteed.We have focused on two central mechanisms: (1)a distributed network temporal tracking systemand (2) a deadline-based forwarding algorithm.These two techniques are analogous to therouting and forwarding in the current IP layer,where the routing components are responsiblefor efficient collection and propagation ofaccurate network connectivity information andforwarding components focuses on fastforwarding of packet based on the collectedinformation. In this research we demonstrate thatwe might be able to infuse deep algorithm inrouters for intelligent networking with theemphasis of deadline conformant packetforwarding. This paper presents an efficientdeadline based forwarding queue-schedulingalgorithm.Now that we have focused on the generalprecepts of our approach, we will now move tosection two, where we present the overview ofthe CRP shell base architecture for routerextension that enables the researcher to plug-inan algorithm of interest. In section three, wepresent the CRP routing model which illustratesthe forwarding and route lookup prototype. Insection four, we present a CRP based routingsolution, which provides a fast polynomialalgorithm for deadline based routing. Finally,The details of our experiments implementationsand comparison results and analysis for variousheuristics are presented in section five.2CRP ModelThe Constraint Resource Planning (CRP) is amethodology that enables the design of nearoptimum approximation algorithms- with linearexecution shell loop. In applied AI and planningresearch, a large body of knowledge exists forfast approximation algorithm of NP-hardproblems [8,10]. We have selected the CRPmethodology because of its ability to become ageneric execution shell (interface) that serves thepurpose of this paper. The CRP divides thesolution of a complex NP-hard or NP-completeproblem into two decision heuristics: i) mostcritical task heuristic HMCT() and ii) the leastimpact solution heuristic HLIS()[5,10]. CRPprovides a polynomial time bound executionshell called the CRP engine that uses theheuristic to generate powerful near optimumsolutions based on the proposed solution withinthe CRP shell.Candidate TasksGet New TasksCriticallyHeuristicSolveLeast Impact SolutionLeast ImpactHeuristicMost Critical TasksGenerateSolutionsCandidate SolutionsFig – 1: The generic CRP engineCRPprovidesadomain-independencesystematic framework to solve constraintsatisfaction problem in planning and scheduling.CRP provides very competitive near optimumsolutions for more than fifty problems includingtraveling salesman, job shop scheduling, andmap coloring to enhance triangulation tooptimum packing [18]. It divides any constraintsatisfaction-planning problem into a four-cornerexecution model as shown in figure 1. We have
Proceedings of the 13th IEEE International Conference on ComputerCommunications and Network, ICCN04, October 11-13, 2004, Chicago, pp93-100designed an intelligent routing shell that isexpected to host or facilitate various intelligentrouting solutions. We shall present the solutionspecific for delay-bound communication.The advantage of CRP is that within this genericfour-corner shell the optimization criterion canbe radically changed just by changing these twoheuristics. This feature enables one to use it as abasis for extensible routing. Interestingly at thesame time, it helps one to experiment with wildnumber of probable heuristics pairs in short time.We have formulated a number of candidateheuristics for each of those heuristics and haveexperimented with over fifty combinationprobable heuristics.CandidatePacketsGet NewPacketsTransmitLeast ImpactQueueSelect theMost CriticalPacketAccording ToThe SelectedSchedulingAlgorithmSelect theLeast ImpactQueueAccording toThe SelectedQueuingAlgorithmMost CriticalPacketSelect ASchedulingAlgorithmList ofSchedulingAlgorithmsGenerateAssignment to allQueuesCandidateQueuesSelect AQueuingAlgorithmList ofQueuingAlgorithmsFig – 2: data flow diagram of the CRP-Interface for thedeadline-base routing. Each heuristic decision boxfacilitate a pluggable action.2.1 CRP Interface BlocksThe interface consists of four data blocks, twoheuristic decision points, and three mechanicalprocedures. Those procedures remain unchangedand are not affected by various algorithms whichare plugged in the heuristic decision points. Thesetup of our research CRP interface is shown infigure 2. At the entry stage of the interface,packets which are ready for transmission areinserted into the Candidate Packets data blockwhich is the first mechanical procedure. The firstheuristic decision point decides which packet isthe most critical based on the plugged schedulingalgorithm. Now the most critical packet isinserted into the Candidate Packet data block.The second mechanical procedure is theexecution of a cost function which will estimatethe arrival time of a packet based on networkpropagation information on a specific queue. Thearrival times of all the available queues for themost critical packet are the candidate assignmentsolutions. Then these solutions are inserted themin the Candidate Queue data block. The secondheuristic decision point selects the queue that hasprovided the “best results”. The definition of the“best results” is decided upon by the pluggedqueuing algorithm. Once a queue is found tohave produced the best results, it is inserted intothe Least Impact data block. At this point, thethird mechanical procedure proceeds to transmitthe most critical packets via the least impactqueue. The next cycle of the CRP shell startsafter this transmission.3Deadline Base RoutingThe CRP shell act as a host to various schedulingand queuing heuristics. We have defined manyscheduling algorithms which may be plugged inthe admission control heuristic and, also, havedefined many queuing algorithms which can beplugged in the forwarding heuristics.3.1 SchedulingThe object of the scheduling policy is to select apacket from the input queue using the mostcritical-task heuristic HMCT() of CRP. Thealgorithm is executed in a cyclical executionmode while the router is up and running. At mostn packets are inserted in the input queue. Thenthe packets in the input queue are evaluatedaccording to the scheduling heuristic. The routerwill enter into a phase where all the packets inthe input queue are forwarded before allowingany other packets into the input queue. Once apacket is selected, it is removed from the inputqueue for transmission. The transmission is theresponsibility of the queuing model, where aqueue is selected based on the queuing modelheuristic. The scheduling model is in table 1. While the router is runningIf there is no outgoing packet in the router Wait until at least one packet arrive in the router For a fixed time interval or n or more packets are in the router Insert at most n packets in the input queue (packet insertion is inaccordance to their arrival time) (Within the input queue) Retrieve all the packets’ deadlines While the input queue is not empty Select the most critical packet according to the scheduling heuristic Remove the selected packet from the input queue Run the queuing algorithm to transmit the selected packet Table–1: The CRP scheduling model Packet’s end of transmission time – is the time used to deliver the packet.Packet’s real penalty – is the positive difference between the end oftransmission time and the deadline if the end of transmission time is largerthan the deadline.Gross penalty – is the accumulated real penalties after all the packets aretransmitted.Queue’s expected end of transmission time – is the time that the queuingmodel produces which is the assumed time of deliveryQueue’s hop number – is the iterative order of hops in the queue.Queue’s hop count – is the number of hops in the queue.Chosen queue – is the queue that is assigned to deliver the packet.Hop flight time – is the time used to transmit a packet fully over this hop.Hop activity – is a special value which is retrieved from the network. Eachtime a packet is transmitted through this hop, the hop flight time isrecorded. The hop activity is the accumulation of all the flight timesthrough this hop.Hop number cost time – is produced by the first part of cost function andis a parameter of final part of the cost function that produces the expectedend of transmission time.Hop activity cost time – is produced by the first part of cost function andis a parameter of final part of the cost function that produces the expectedend of transmission time.Table–2 The terms of the queuing model
Proceedings of the 13th IEEE International Conference on ComputerCommunications and Network, ICCN04, October 11-13, 2004, Chicago, pp93-1003.2 QueuingThe objective of the queuing policy is to assignthe selected packet to a queue using the leastimpact solution heuristic HLIS(). The queuingpolicy uses a network cost function, explainedlater, to determine which queue produces theleast impact solution.3.2.1 Model TermsPrior defining the queuing model, we mustexplain some of the terms used inside the model,see table 2.3.2.2 Queuing ModelThe queuing model is implemented for onepacket and many queues which will compete todeliver this packet, see table 3. If there is at least one queue to transmit the selected packet to itsdestination router For each of all the available queues to the packet’s destination node Retrieve the hop count and the available bandwidth of each hop Compute the expected end of transmission time Select the least impact queue according to the selected queuingheuristic Transmit the packet Send the packet via the chosen queue Retrieve the end of transmission time Increase the gross penalty by the chosen packet’s real penalty (if any) ElseSchedule this packet for later delivery (not reachable in our research)Table–3: The CRP queuing model3.2.3 Cost FunctionThe cost function will produce a single value thatrepresents the expected end of transmission timefor a single packet. The cost function’s mainvariables are the queue’s hop count and thequeue’s hop activity. The cost value growsexponentially as the hop count increases whereasthe bandwidth has a moderate influence on thecost value. Initialize the expected transmission time to zeroFor each hop numberHop number cost time is the area of the circle with radius 2 raised thepower of the queue’s hop number.Hop activity cost time is the hop activity multiplied by the area withradius that is equal is the hop number.Add both cost times to the expected end of transmission time.Table–4: The cost function3.3 Solution FrameworkBelow we present the total solution frameworkwhich explains the scheduling model, queuingmodel, and the cost function in details.3.3.1 Scheduling Frameworkw be the number of packet/s in the router butnot in the input queue at any timeSet of n packets to transmitEach packet, pi where 1 i n,has size, sirequires transmit time, timust be transmitted before a presetdeadline, di 3.3.2Queuing Framework Set of m queues, at most, for each packetEach queue, qj where 1 j m, has an ei,j be the expected end oftransmission time for packet pi via queue qj ci be the chosen queue number j, as in queueqj, which will transmit packet pi i.e.(1)ci j pi qj Ti,j be the packet’s end of transmission timefor packet pi via queue qjli' and li be the gross penalty of all queuesbefore and after packet pi's arrivalrespectively i.e.i 1l i' (Tb, j d b ) if (Tb,j – db) 0 j(2)b 1li i (Tb 13.3.3b, j db ) if (Tb,j – db) 0 j(3)Cost Function Framework hj be the queue’s hop count for queue qjrnj.k be the radius used for the hop numbercost time at kth hop in queue qj. i.e.,rnj.k 2k where 1 k hj(4) raj.k be the radius used for the hop activitycost time at kth hop in queue qj. i.e.,raj.k k where 1 k hj(5) Aj.k be the hop activity of the kth hop in queueqi CNi.j.k is the hop number cost time for packetpi via queue qj at kth hop. i.e.,(6)CNi.j.k π*rn2j.k where 1 k hj CAi.j.k is the hop activity cost time for packetpi via queue qj at kth hop.(7)CAi.j.k Aj.k * π * ra2j.k where 1 k hjhjei,j (CA i . j . k CN i . j . k )(8)k 14DML Algorithms4.1 DML OverviewOur proposed algorithm is called DeadlineMinimum Leverage (DML) algorithm. Thisiterative algorithm consists of two principalphases – Scheduling and Queuing. These twophases represents the task generation andsolution set generation phases of CRP which ispresented in figure 2.
Proceedings of the 13th IEEE International Conference on ComputerCommunications and Network, ICCN04, October 11-13, 2004, Chicago, pp93-100HMCT(){While router is runningIf w 0 {- While the input queue size n and w 0{Insert earliest packet residing outside the input queue in the input queueDecrement w by 1}- Retrieve the deadline value for all the packets residing in the input queue- While the input queue is not empty {Select the Most Critical Packet according to the selected scheduling heuristicRemove first packet from the input queue}}}Table–5: The CRP scheduling algorithm pseudo code.4.1.1 DML SCHEDULINGOnce the packets are inserted in the input queue,the DML scheduling algorithm will sort allpackets within the input queue in a descendingorder according to their deadline. The selectionprocess is to pick the packet sitting on top of theinput queue which is the packet with highestdeadline. Now, this packet is the most criticalpacket.HLIS(){If m 0 {For j Å 1 to m {ei,j 0For k Å 1 to hj {rnj,k 2kraj,k kCNi,j,k π * rn2j,kCAi,j,k Aj,k * π * ra2j,kei,j CNi,j,k CAi,j,k ei,j}}Select the least impact queue according to the selected queuing heuristicIf Ti,ci dili Å l’i (Ti,ci – di)}}Table–6: The CRP queuing algorithm pseudo code4.1.2 DML QueuingThe DML queuing algorithm requires a few extraparameters, see table 7. Queue’s leverage time – is the positive difference between the expected end oftransmission time and the deadline if
Resource Planning (CRP) methodology for algorithm designs. The resulting near-optimum algorithm operates within an extensible CRP shell and uses two pluggable scheduling and forwarding heuristics to produce near-optimal performance. In this paper we present the shell architecture, the algorithm, and the simulation
Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original
Street Asphalt Overlay History September 3, 2019 SEGMENT STREET FROM TO ACTIVITY DATE SS‐000137 04TH AV F ST E ST AC Overlay 2/5/2014 SS‐000140 04TH AV ISLAND AV MARKET ST AC Overlay 11/25/2013 SS‐000141 04TH AV J ST ISLAND AV AC Overlay 11/25/2013 SS‐000142 04TH AV K ST J ST AC Overlay 11/25/2013
February 2006 Overlay Utility 7-1 7. Overlay Utility IRIS has a flexible overlay feature for drawing overlays, or maps displayed on top of other IRIS/Open products. Overlays are used for product output and the real-time display. The overlays used in product output are specified in the Overlay menu. An overlay can consist of the following:
Intro to Overlay Maker Mac Tutorial IntelliTools, Inc., 1720 Corporate Circle, Petaluma, CA 94954-6924 Materials may be freely reproduced Rev. 12/8/98 Phone: 800-899-6687, Fax 707-773-2001, Email: info@intellitools.com Page 7 of 7 13. Use Your Content-Only Overlay Quit Overlay Maker . Send the overlay by double-clicking on the
10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan
service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största
Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid
LÄS NOGGRANT FÖLJANDE VILLKOR FÖR APPLE DEVELOPER PROGRAM LICENCE . Apple Developer Program License Agreement Syfte Du vill använda Apple-mjukvara (enligt definitionen nedan) för att utveckla en eller flera Applikationer (enligt definitionen nedan) för Apple-märkta produkter. . Applikationer som utvecklas för iOS-produkter, Apple .
