IntroductionRouting ProtocolRouting TablesRouting MetricsDynamic Vs Static routingDistance Vector Protocol Vs Link State ProtocolProblem StatementProtocol SpecificationTopology EstablishmentRouting UpdatesMessage FormatServer Commands/Input FormatServer Responses/Output FormatCS 640 Introduction to Computer Networks Fall 2005http://www.cs.wisc.edu/ ∼640-1/index.htmlProgramming Assignment 3: Routing ProtocolAssigned: October 25, 2005 Due: Nov 10, 2005, 11:59pm1 IntroductionRouting is the main proc e ss used by Internet hosts to deliver packets. Internet uses a hop-by-hop routingmodel, which means that each host or router that handles a packet examines the Destination Address in theIP header, computes the next hop that will bring the packet one step closer to its destination, and deliversthe packet to the next hop, where the process is repeated. To make this work, two things are needed. First,routing tables match destination addresses with next hops. Second, routing protocols determine the contentsof these tables1.1 Routing ProtocolThis is a software running on top of routers to determine the appropriate path onto which data should beforwarded. The ro uting protocol also specifies how routers report changes and share information with theother routers in the network that they ca n reach. A routing protocol allows the network to dyna micallyadjust to changing conditions, otherwise all routing decisions have to be predetermined and re main static.1.2 Routing TablesInternet hosts use routing tables to compute the next hop for a packet. Routing tables can take many forms,but here is a simple model that can explain most Internet routing. Each entry in a routing ta ble has at leasttwo fields - IP Address Prefix and Next Hop. The Next Hop is the IP address of another host or router thatis directly reachable via an Ethernet, serial link, or some other physical connection. The IP Address Prefixsp e c ifies a set of destinations for which the routing entry is valid for. In order to be in this set, the beginningof the destination IP address must match the IP Address Prefix, which can have from 0 to 32 significantbits. For example, a IP Address Prefix of 128.8.0.0/16 would match any IP Destination Address o f the form128.8.X.X.1.3 Routing MetricsRouting metrics are a scoring system for routes a routing device knows. Metrics are calculated by routersto prioritize routes fro m best to worst. Routers use the metrics to select the best possible routes to a givendestination. Metrics can include hop co unt (how many stops there are b etween here and the destination),media type (Serial, Ethernet, SONET etc.), availability (whether the machine is up or down) and severalother factors including some set by the Network Administrator. A lower metric generally indicates a betterroute.1.4 Dynamic Vs Static r out ing• Static Routing: Static routing is not really a protocol, simply the manual entry of routes into therouting table via a configuration file that is loaded when the device starts up. Static routing is thesimplest form of routing, but it is manual and does not work well when it has to be entered on a largenumber of devices. It is also does not handle outages or down connections well, as the manual entrieswill have to be changed manually to recover from such a loss of connectivity.1• Dynamic: Dynamic routing protocols are software applicatio ns that dynamically discover destinationsand how to get to them. A router will ’learn’ routes to all directly connected networks first. It willthen learn routes from other routers that run the same routing protocol. The router will then sortthrough it’s list of routes and select one or more ’best’ routes for each destination it knows or haslearned. Dynamic proto c ols will then distribute this ’best route’ infor mation to other routers runningthe same protocol, thereby extending the informa tion on what netwo rks exist and can be reached. Thisgives dynamic routing protocols to adapt to network topology changes or outages ’on the fly’. Onceall routers know all routes to all destinations, the routing pr otocol has said to have ’converged’. If auser were to attempt to reach a destination before the routing protocol c onverged, the packet wouldeventually re ach a dead end: a router which does not know how to get to the destinatio n, and thepacket would be dropped.1.5 Distance Vector Protocol Vs Link State Protocol• Distance Vector Protocol:This type of routing protocol requires that each router simply infor mits neighbors of its routing table. For each network path, the rec e iving routers pick the neighboradvertising the lowest cost, then add this entry into its routing table for r e -advertisement. Hello andRIP are common D-V routing protocols.• Link State Protocol:This type of routing protocol re quires each router to maintain at least a partialmap of the network. When a network link changes state (up to down, or vice versa), a notification,called a link state advertisement (LSA) is flooded throughout the network. All the routers note thechange, and recompute their routes accordingly. This method is more reliable, easier to debug and lessbandwidth-intensive than Distance-Vector. It is also more complex and more compute- and memory-intensive. OSPF and OSI’s IS-IS are link state routing protoc ols.1.6 Problem StatementFor this part of the assignment, you will implement a simple routing protocol on lines of Distance VectorProtocol to be run on top of servers (behaving as routers). The servers communicate with each other basedon routes established via routing protocol updates. The server will run on a machine at a defined portnumber. The servers will communicate with e ach other using routes established by the routing protocol.2 Protocol SpecificationThe various components of the protocol are explained step by step. Please strictly adhere to the specifications.2.1 Topology EstablishmentEach server is supplied with a ”top ology file” at startup that it uses to build its initial routing table. Thetopology file is local and contains the link cost to the neighbours. For all other servers in the network, theinitial cost would be infinity. The topology file looks as fo llows:• h num-server i• h num-neighbours i• hserver-IDi hserver-IPi hserver-porti• hserver-ID1i hserver-ID2i hcostinum-servers: number of serversserver-ID: An unique identifier for a serverserver-IP: IP address of a serverserver-port: port of a server2cost: cost
View Full Document
Unlocking...