aiaexams.myfanforum.org Forum Index aiaexams.myfanforum.org
solutions for aia exams
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   Join! (free) Join! (free)
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

aufgabe 4

 
Post new topic   Reply to topic    aiaexams.myfanforum.org Forum Index -> februar 2006
View previous topic :: View next topic  
Author Message
admin
Site Admin


Joined: 12 Feb 2008
Posts: 52



PostPosted: Tue Feb 12, 2008 3:51 pm    Post subject: aufgabe 4  Reply with quote

distance vecotr routing:

O(n) - each router sends just one packet over the fastest link

link state routing:

O(nk) or O(sum(Ni*Ki)), router use flooding, so that each packet is sent to each neighbour.
Back to top
View user's profile Send private message Send e-mail
semyon



Joined: 13 Feb 2008
Posts: 44



PostPosted: Wed Feb 13, 2008 10:19 pm    Post subject: Reply with quote

i don't agree:

in dist. vector routing, each node sends a package to each neighbour
--> complexity is O(n*k).

link state routing uses flooding
--> flooding: O(2*e-n+1) where e:#edges, n:#nodes.

semyon.
Back to top
View user's profile Send private message
admin
Site Admin


Joined: 12 Feb 2008
Posts: 52



PostPosted: Mon Feb 18, 2008 3:11 pm    Post subject: Reply with quote

finde ich nicht so ganz...

also, bei LSR hast du ja flooding, d.h. jedes packet wird vom rooter an alle gesandt, ausser an den, der es geschickt hat. somit sendet der erste router n-1 packete, der jeder nächste n-2 packete, so ist es auch in aufgabe 3, im home ass. 2 beschrieben, so dass

die komplexität von LSR bei O(n²) ist.

bei DVR wird aber ein packet nur an den nähesten nachbarn gesandt. somit eine Komlexität von O(n*k)...
Back to top
View user's profile Send private message Send e-mail
JB



Joined: 14 Feb 2010
Posts: 7



PostPosted: Sun Feb 14, 2010 2:30 pm    Post subject: My solution Reply with quote

Distance Vector Routing:
every one of the n nodes sends to k directly linked nodes his distance vector.
=> O(n*k)

Link State Routing (uses flooding):
every one of the n nodes sends to k nodes his vector and receives k packages which he has to forward to k-1 nodes (k are conected to him, 1 of them is the one from which the package has come from)
=> n * [ k + k *(k-1) ] = n * [ k + k² - k ] = n*k²
=> O(n*k²)

Is there still anyone here to confirm?

Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    aiaexams.myfanforum.org Forum Index -> februar 2006 All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Card File  Gallery  Forum Archive
Powered by phpBB © 2001, 2005 phpBB Group
Create your own free forum | Buy a domain to use with your forum