Types of random algorithms

There are random algorithms that always produce a correct result called Las Vegas Algorithms. There are Monte Carlo algorithms, random algorithms that have a margin for error that can be made as small as required (one of my lecturers at the university proclaimed that once you reach 2^-300 - usually not very hard, you have a better chance to locate a specific atom in the universe). Both of these use some random way of accessing the problem. I though, would like to discuss statistical algorithms, which are algorithms that do not use random number generators, but instead rely on the input to be sufficiently random. They may not always produce the best result, but in the long run, they produce good enough results, especially since they are far more efficient than the perfect algorithm.

Take sorting a stream of random elements for example. Sorting efficiently takes a little memory overhead and can be done with logarithmic efficiency. What if we don’t really need perfect sorting? What if we just require that the smaller elements be separated from the others? That can be done with constant efficiency - just deciding if the element is one of the smaller ones or not. Of course, we need to decide where we draw the line between small and large elements. We could do so statistically, for instance, start with some arbitrary number and for every element processed, add one if it is larger than the limit and subtract four if it is smaller than the limit. After some time, we will be very close to separating the smaller 20% of the numbers. Moreover, the limit will adapt to changes in the input: if we suddenly start getting larger or smaller elements, the limit will shift to its steady state: 20% of the time it will be lowered by four and 80% of the time it will be raised by one, hovering around the same number.

The solution displayed above is not correct all the time, but if the input is random enough, it will give good results most of the time. The trick when using statistical algorithms is to accumulate the good results and try to reiterate the incorrect results. In the best case, an accumulation of good results that can be detected and separated, allowing the algorithm to improve its work. Such is the case of memory fragmentation.

Efficient Allocation

One of our protocol stacks here at RADVISION, MEGACO, suffered from a memory fragmentation problem. It uses dynamic memory allocation, and in some of the operating systems, allocating and freeing small memory sizes degrades performance over time. It became necessary to manage the way memory is allocated. We created a memory manager that allocated large memory sections (we called them “pages”) and divided each page to smaller allocations (called “blocks”). Memory allocations were rounded up to the nearest block size and when pages were filled up, new pages were allocated.

The problem was with freeing memory: we could only free a page when all the blocks in it were freed. At the same time, we needed to allocate memory from the same pages. A perfectly correct algorithm would need to keep a sorted list of the pages by their fullness, and allocate from the fullest page only, or perhaps consider the relative allocation times. These lists should be resorted on each allocation and freeing of a memory block, hindering efficiency. We decided to create an algorithm that would be mostly correct, but much more efficient. We divide the pages into four bins by fullness, and we allocate memory from the bin with fullest pages first. We assume that memory freed could belong to any page, so by allocating memory from the fullest pages, we allow pages that are vacant to free up until they are empty and can be released. The division to bins then helps memory pages that are partially vacant to continue the process until freeing up completely.

Let’s study the algorithm: memory load rises, so more memory is allocated. We keep allocating pages and allocating from them. Each new page starts at the freest bin and moves to the fullest. Then we stay around the peak load for a while and memory is freed and allocated constantly. Almost all the pages will remain in the fullest bin. Now the load decreases somewhat so pages start freeing up. As soon as a page drops from the fullest bin to the not-so-full bin, no allocations will be made from it - there are enough pages in the full bin. This is what I called “separation of good results” earlier. Pages that dropped to a lower bin should keep moving through the bins as old memory is freed and new memory is allocated only from the full bin. At this stage, there is a significant memory overhead, but this would be the case even if our algorithm used the best predictions, and in the long run, our algorithm will achieve almost the same results.

Similar Applications

• Branch prediction schemes
• Reinforcement Learning
• Optimal Control

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• The Zen Pointer (0)
• The Void Pointer (0)

No elves or reindeers were harmed in the making of this blog post…

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• No related posts.

What is Jitter?

A quick statistics reference, over an IP network, packets sent are always received in the same order that they were sent in or with the same latency. For simplicity sake, we’ll look at the time between sending and arrival of a packet as a random variable with a normal distribution. The mean of the distribution correlates to the network delay and the variance correlates to the jitter.

Our mission when we construct the Jitter Buffer is to re-evaluate the Jitter constantly in order to provide minimum delay with minimum unnecessary packet loss - packets that would have arrived if we waited for them.

The easiest way to fix jitter is to simply store data packets as they are received, reorder them if necessary, introduce a delay into the system that will let all (or 99%) of the packets arrive, and then replay them at the required speed. Waiting too long means the result won’t be as useful for real-time communications. On the other hand, not waiting long enough means we’re going to lose some packets along the way, which reduces media quality.

As we’re working with networks, the jitter isn’t static and changes when others use the same network (think internet). This is why the jitter buffer needs an ‘A’ - it needs to be adaptive.

How to be Adaptive?

I guess that’s the real question, isn’t it? You must introduce more delay if you miss packets and must then remove that delay if packets start arriving more rapidly. I won’t take you through our state machines and algorithms, but I will point out a few corner cases that deserve some thought when implementing an AJB:

• Pause/Resume: the RTP stream may pause (’mute’ was used or when silence is detected) and later resume. How do you differentiate this from jitter? How do you know not to introduce too much delay when the stream resumes?
• Source switch: sometimes the source of the media stream changes in the middle, perhaps some relay point starts streaming a “ringing tone” video, which is later replaced by the real source video. The new stream’s timestamps and sequence numbers may be higher or lower than the previous stream’s timestamps and sequence numbers (or one lower and one higher). How does the AJB detect the source switch? Does it remove all packets of the old source or try to sequence them one after the other? And what if the streams get mixed?
• Too many packets: what if there are too many packets? Maybe the thread is starved or the codec is hung? Will packets be removed from the front? From the back? Maybe the AJB should recognize some kind of problem and clear the queue?

AJB Ecology

The AJB is not alone in the world. On one side of it is the network, on the other side is the codec. From the network it receives a stream of packets, some missing, some reordered. To the codec, it must supply an ordered, a correctly timed stream of packets. There are other elements working with the AJB, like Lip Synchronization mechanisms or even Forward Error Correction (FEC):

• Lip Sync means the synchronization of the audio source with the video source. Since the AJB is already balancing delays and ordering timestamps, it could easily take care of synchronizing multiple streams. The only thing is - you’ll need to manage it to do so.
• Forward Error Correction algorithms send additional packets to reconstruct lost packets; usually the FEC packet is the XOR of a few RTP packets. However, the reconstruction of an RTP packet is a costly process, locating the needed packets for the reconstruction and running XOR on the buffers to reconstruct the lost packet. The AJB can be a good indicator as to when a reconstruction is needed, when a packet is extracted and the next packet to be extracted is missing. The AJB can also signal the FEC module to try and reconstruct it.

The development and integration of an AJB should always consider the environment to which it is added. While expectations like “no additional delays” are unrealistic, expectations like missing packet detection and reconstruction, stream synchronization and resilience to unusual or extreme circumstances are not only realistic, but are critical to the addition of an AJB in your system.

If you’re looking for a jitter buffer implementation, drop us a line or give us a call, we will be having it available shortly for customers.

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• What Type of SDK API Fits Your Development Needs? (0)
• The Last Universalist of VoIP (0)
• Follow Standards – Receive Coupon! (details inside) (1)
• 5 must-have tools for VoIP Developers (1)
• 4 Gotcha’s of text-based protocols (3)

For example, once SIP was said to be a simple communication protocol, far more simple than the colossal H.323. Its success over H.323 is mainly attributed to the steep learning curve for understanding H.323, too steep for mere mortals (I, as a supreme being, can establish H.323 communications telepathically). However, SIP’s days of simplicity are long gone. Nils Ohlmeier kindly provides us with a graph of SIP-related RFC count over time:

I see a pattern here. It would seem (albeit unscientifically) that the more popular a protocol is, the more complicated it will become through extensions and additions.

Simple & Stupid

You might say if the situation was reversed, and H.323 was the popular protocol, it would have been even more complex than SIP, since SIP started out simple, and H.323 started out complex. I say that H.323 started out by establishing principles and using existing sub-protocols (hence the initial complexity), which made it more mature right from the start, and it would have required less extensions than SIP in the long run. Moreover, since H.323 is more rigidly layered and structured than SIP, such extensions usually require less effort to implement. But I’m being bitchy. SIP was light and simple, H.323 was colossal and complex. SIP wins, H.323 FAIL. Woe to us all.

You see, SIP was not built to win. SIP was built to be light and simple, and when all these RFCs were created on top of it, it simply broke. SIP is no longer light and simple; SIP is a whole mess of fragments and jagged edges, glued together by hundreds of conventions and know-how. Why am I thinking of “Katamari Damacy” all of a sudden?

Where Did TCP Go?

When was the last time you gave TCP a real thought? A thought like “I wonder if the TCP connection closed gracefully?” or “Maybe that last packet didn’t get ACKed”. It’s not that TCP is so simple and trivial; there are extensions for high performance, Nagle algorithm, congestion control, slow start, etc. Perhaps the reason it works well enough to be mostly invisible is in the layered structure of it: it will provide nearly the same service to the layers above it and looks nearly the same as the layers below it. It’s not that there is no differentiation between implementations; our “Common Core” team would have had a much easier time if it didn’t, but it is interoperable enough that there is no real problem communicating between implementations of it.

The problem may be that SIP was not layered enough. H.323 also was probably not layered enough. By “layered enough”, I mean layered enough to disappear from sight, to allow anything constructed on top of it to use it blindly. When a protocol comes along that would allow building an application on top of it without any knowledge of it, I’ll know we have something.

The New Kid

The Extensible Messaging and Presence Protocol (XMPP) is coming, and it has money. It was built as a framework to be extended as a stepping-stone to reach for voice and video communications, file transfer, streaming, location and whatnot. It was not built to be invisible. Any extension must know the layer below it, any application built must understand how everything works inside. This may change: a service framework built on top of it may make it invisible, or in may crumble under the weight of its extensions to become like SIP. Time will tell.

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• Why is VoIP so hard on firewalls and NATs? (1)
• Why text-based protocols hurt your design (4)
• Empty Security & Vitamin Cookies (0)
• 5 Ways to Solve NAT Traversal for VoIP Protocols (0)
• The binary of text protocols (2)

• The antivirus software (AVG antivirus) refused to update its virus database. After trying to connect for about one second, it would declare that I do not have an internet connection. Sometimes it would corrupt its own databases in the process.
• My iGoogle homepage would start to load, and then the browser would claim that the server reset the connection. At first I thought it was some applet or another, but each applet worked fine separately, only when the whole page was loaded did it reset the connection.

This brings me to the issue of timeout in communication products.

How long should you wait?

Many standards define message timeout. ITU-T’s H.225 standard (part of H.323) recommends 3 to 5 seconds of RAS timeout, with 1 or 2 retries, depending on the message. RAS also implements the Request in Progress (RIP) mechanism to notify the sender that his request was received and will take longer to process. MEGACO also has a similar mechanism. When using TCP, the transport control should be the one notifying of failed communications or dropped connections. Why do implementers decide on low timeout values?

Most of the time, the argument used for lower timeouts is the theoretical user: the user cannot be expected to wait. They quote the 8-second rule, saying that if there’s nothing on the screen for 8 seconds, the user gives up. One wonders how people get through starting up their computer before giving up and going to watch TV (check it out: instant-on). Jokes aside, there is a limit to user patience. Shorter timeouts produce a ‘peppier’ response, feeding the user’s need for instant gratifications: Is it working? Did it fail? Should I reboot? Should I try something else? My antivirus’ update program was so anxious to give me results that it didn’t realize better results might arrive had it waited a few more seconds - and I really wouldn’t have minded.

What I’m saying is that even in today’s fast internet, client developers should set generous timeouts. You never know if security measures, billing systems or cellular networks may impose latencies on connections. The question should not be how long the user will have to wait. The user can decide that for himself by canceling the process. The question should be, what is the alternative. If, like my antivirus, all it can do after the timeout is report the failure, the client should wait longer, or even as long as the user allows it. My media player, for instance, notifies me that it is connecting and counts the seconds until giving up (the timeout is configurable). The user may be expecting to see something within 8 seconds, but it’s not necessarily the final result, sometimes a progress bar is enough.

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• Four Sons of VoIP security (0)
• Your Product Manager’s Configuration and You (15)
• Why is VoIP so hard on firewalls and NATs? (1)
• System Security Through System Breakdown (0)
• Standards? Pul–lease! (1)

We, the people of Troy

The city of Troy was a secure system. They had strong walls, alert guards, and were well trained, until this appeared:

The Trojans clicked “Run” without even reading Laocoon and Cassandra’s warning, and to this day, Trojan horses, bunnies and lolcats are wheeled through the walls. Maybe we should stop it. Stop building walls, that is.

We, the people of the Web

They promised me a network computer. They really did. A dumb terminal that I’ll touch with my thumb and it will immediately access all my services from the web. Let’s assume they will make good on that promise. Now, will it be more, or less secure? Obviously, it won’t be as secure as a personal computer that is not connected to the web. Let’s assume that every computer is connected to the web and assume that they are very well protected, except for security risks caused by the users themselves. That’s a very lenient assumption, so let’s be kind to the net terminal as well. We’ll assume that data, kept remotely, is secure from attacks and can only be accessed by its rightful owner. We will also assume that all services currently enabled on the net terminal are non-malicious. That last assumption is not enough because we have to assume also that every service enabled is also safe from attacks, meaning that it is impossible to hack into the service itself or fake the service’s certificates.

Now we are offered a new service called Trojan Horse. It’s a cool service that shows a horse on wheels rolling on the task bar, ejecting dancing bunnies every now and then. How will this look like on the net terminal? Maybe something like this:

You may notice that I have a lot of control here. I could allow some application to use the screen (for a limited time), deny it the speakers if I’m at work or ask to run it anonymously. This will create a negotiation between the running program and the user, perhaps notifying it that the application cannot run without access to personal settings. Now that I do not have one central wall blocking access to my computer, I have little walls blocking access to each resource type. I can use these little walls to control programs even after they have been installed, for instance, if I am notified that the software is about to release Greek soldiers and take over my system (which I have not yet granted it permissions to do), I could deny it.

Better living through more protocols

The real beauty of this is that all the technology for cloud computing and authorized access to resources exists today, only not at the right place. Billing systems do it all the time: authenticating users, consuming resources, tracking usage. The Diameter protocol, for instance, can be used just as well when protecting system resources. Applications can authenticate themselves, consult local policy servers, request and consume resources. They can be tracked and permissions to abusive programs can be revoked.

Does this solve the “dancing bunnies” problem? Not immediately, but it does allow the system to monitor and locate abusive programs and then alert the user, so on the long run, they will be found and removed. This can also be done in current systems, but since it is not broken down into components that communicate with each other, it will require many resources just to keep track of everything - which might be worse than drunken Trojans. When it comes to controlling which programs are allowed what access to your resources and personal data, a network computer is safer than a desktop computer. If we consider that sometime in the future we’ll carry our personal data on a mobile device and use such terminals just to access remote information or use cloud computing services, our personal data is likely to be much better managed than it is now.

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• Why is VoIP so hard on firewalls and NATs? (1)
• Secure System, Secure User (0)
• Logs + Scripts = Ownage (0)
• Four Sons of VoIP security (0)
• Empty Security & Vitamin Cookies (0)

It’s a description of what happens when a user receives an email message that says “click here to see the dancing bunnies”.

The user wants to see the dancing bunnies, so they click there. It doesn’t matter how much you try to dissuade them, if they want to see the dancing bunnies, then by gum, they’re going to see the dancing bunnies. It doesn’t matter how many technical hurdles you put in their way, if they stop the user from seeing the dancing bunny, then they’re going to go and see the dancing bunny.

Dance, Bunny! Dance!

The original discussion back then was as to the need for antivirus. Today we regularly use antivirus, adware removal, spyware detection, anti-phishing, spam filters, firewalls, server-side protection, permission management, homepage kidnapping prevention, internet zones and site certificates, and people still want to see the dancing bunnies! Only problem is, their PCs are so slow due to all the security software that they can’t get it running.

Now, what if we were just walking down the street and someone said “Hey, bud, want to see some dancing bunnies?”

You’d probably run like hell, won’t you? Look INSIDE the box? What are you, crazy or something? Every alarm system in your head will go off if someone just came towards you looking like that. The problem is, we don’t see emails and web pages as shady little guys with gray trench coats and hats going “Hey, bud”. We’re too used to TV and books, and TV and books can’t hurt you, can they?

Whom Can You Trust?

When I access my work mail from the web, I get a security warning about an expired certificate. That’s OK; our IT goes “that’s our warning”. Just confirm it anyway. Internet Explorer warns me every time, while Firefox lets me set a permanent exception, so I’m using Firefox for mail access even though it looks a little strange. My OS warns me about running any file that’s not local, and the first time I run a file I downloaded.

It really does beat the point, does it? On one side, there are all these friendly interfaces and authoritative messages, on the other side, tired warnings and checkboxes that say, “Always allow”. Besides, we really do want to see the dancing bunnies.

I don’t even believe in the “virtual sandbox OS” suggested by Jeff. How about this:

You’d confirm it in a second, because you trust the friendly sites, because you are used to the nice emails from friends sending you dancing bunnies. More dancing bunnies please.

Websites are Strangers in Dark Alleys

Until this realization is hammered deep into the user’s mind, no security can be good enough. We must tap into the same inner protocols that intuitively make us realize danger is about. None of these friendly notifications will do. Here is my suggestion for a warning screen:

The picture will change randomly, of course. If you click on that without considering physical harm, well, bud, you have worse problems than viruses.

Maybe I’m being naïve. What do you think?

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• Why is VoIP so hard on firewalls and NATs? (1)
• System Security Through System Breakdown (0)
• 5 Ways to Solve NAT Traversal for VoIP Protocols (0)
• The human puppet (0)
• Standardized Human Behaviour: Baby boom (1)

What?

You don’t see any difference?

Maybe it’s your RSS feed. Come closer. Look around.

Still nothing?

We changed! A new theme! New widgets! New homepage! New “about” pages (and easier contact forms)!

We even moved to a new host and a new platform (and solved the annoying email notification for comments thing).

Nothing, huh? Sometimes I don’t know why we bother. Well, actually, Tsahi did most of the bother, but we provided moral support. Let me know if there are spots he missed or anything that needs fixing so then we can rub his nose in it. You can also say how nice the new design is, but don’t overdo it, he’s ego’s big enough as it is and we’d appreciate it if it didn’t grow any further.

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• No related posts.

The void pointer is like a general usage pointer, removing the need for container classes and templates, which are commonly used when creating generic data structures such as a list, hash, vector, stack, queue, etc. This same flexibility gives the void pointer its bad rep. Some prefer not to point at objects at all but to copy them instead, and some prefer a system where a reference counter is maintained between all containers. Both are redundant if void pointers are used with care, although a reference counter can be used with void pointers as well. I personally prefer cross pointing: the object should be able to reach any location where it is pointed to. If a hash or a list points at an object, the object should point back to the hash or the list. This makes removing the references when the object is deleted a little easier.

Care and Handling of a Void Pointer

I’m not saying that using the void pointer is easy. In many ways, it requires more care and planning than using templates. I am saying that it is more efficient, less memory consuming and a more flexible way of programming - when used correctly. When misused, void pointers can be cast incorrectly, accessed after the object being pointed to was deleted (any pointer can, but void pointers are move vulnerable since they do not know the object), or just cause confusion and waste time.

Dont’s:

• Don’t overuse void pointers. Sometimes templates are good, and sometimes the use is just too specific to try and make it general-purpose.
• Don’t use them to pass instead of object handles. Object handles carry valuable information about the type of object passed.
• Don’t use them for obfuscation. There are better ways, which are less confusing (see handles, above)
• Don’t pass them between modules without knowing their meaning; this will always lead to confusion, especially when something is changed in either of the modules.
• Never use NULL as a valid value: NULL means “no-value”, if you really have to pass zero as a value, reconsider the use of void pointers.

Do’s:

• A pointer (not just a void pointer) should start out pointing at NULL, and be returned to pointing to NULL once the object is removed.
• Use one instance of a void pointer to point at a single type of object. For instance, if you have a void-pointer-list object, use it for one type of object, create another instance of it for another type and document each instance well. This may seem risky, but the footprint overhead for using templates makes it worthwhile.
• When passing void pointers for usage (i.e. not for storage or as user context), always provide an enumeration serving as a guide to the contents of the void pointer. The receiver will recast the void pointer according to the guide. This will save a lot of trouble should future changes require passing something else.

The Best Advice

Keep your eyes open! The void pointer will require the programmer to know what he’s doing, pay attention to valid and invalid pointers and to where everything is. Before deleting any object that’s pointed to, the object must go over all the places pointing to it and remove them. Whenever using a void pointer to point at anything, go over the checklist:

1. Does the object point back?
2. Does the object know when it is pointed to and when it is not?
3. Does the object remove the pointer to it when it is deleted?

If the answer to any of these is “no”, you’ll end up pointing at a deleted object, which is crushing. One thing’s for sure: it will keep you alert.

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• The Zen Pointer (0)
• No Need to Program Perfection (1)
• Multi Thread Me (1)
• Memory efficiency, the Tertium Quid (0)
• I’m hunting: 4 most important qualities I look for in protocol programmers (0)

I am the Void pointer. Some may fear me. It is their own Void that they fear, their own lack of knowledge. The ones with insight wield me with confidence. The ones who are lacking dangle me and throw me as they spread errors and exceptions all around them. Seek out the true path of the Void pointer; do not hide behind false containers and interfaces, do not raise walls of templates to ward me. I am the Void pointer. Meet me eye to eye.

The True Path

The Tao of the Void pointer is not an easy one. It is full of doubt and uncertainty. Yet the ones with the insight reap its rewards. Eat from the fruit that is plentiful along its road: the fruit of memory, the fruit of agility and the fruit of efficiency. Remember, you who seek the Path of the Void: you are the one who walks. Do not be led by the path or it will lead you to uncharted realms. Always start out pointing at the NULL. Always end up pointing at the NULL. While on the path, always try to point out the same objects: point at a tree to remember the tree, do not point then at a flower lest you think the flower a tree. If you made a chain of Void pointers, use one instance of it for the flowers and another instance of it for the trees. The chain is the same, and its footprint is one, yet I can bind in it any type of object, just be sure to bind one type at a time. I am the Void pointer. Heed my warnings.

You may need a guide when you walk The Path of Void. The Void is a cloak, a veil; it may hide anything in its folds. Such a cloak is very powerful: When a passage is made for an object, it will fit only it and none other, but when a passage is made for a Void pointer, anything can pass through it, covered in the cloak of the Void. When it reaches the other side, it must be called by its name to unravel the shadows of Void. The wise make two paths, one for the Void and one for its guide, so the Void can be called it by its name and the veil removed to reveal the true object behind it. The many are united by the Void, yet still they have many names. I am the Void pointer. Forget my name.

The Master of the Void

The master of the Void must keep his eyes open: the Void knows nothing and sees nothing; all things are one to him. It knows not when memory becomes figment. The master must know all the Void pointers pointing at his memories, and he must cast them away before the memory is forgotten. If he will not, false memories will be dredged up from the Void, crashing down on his head. The master of the Void fears not the Void, for it is his friend and ally. I am the Void pointer. I am your friend.

Download your free eBook guide on Video Conferencing, the Enterprise and You. Post from: Code of Contact

Related posts

• The Void Pointer (0)
• Multi Thread Me (1)
• Memory efficiency, the Tertium Quid (0)
• No Need to Program Perfection (1)
• 4 Gotcha’s of text-based protocols (3)